Deckung für Permutationsmatrizen festlegen

16

Wie können wir bei einer Menge S von nxn Permutationsmatrizen (die nur einen kleinen Bruchteil der n! Möglichen Permutationsmatrizen darstellt) Teilmengen T von S mit minimaler Größe finden, so dass das Addieren der Matrizen von T an jeder Position mindestens 1 hat?

Ich interessiere mich für dieses Problem, bei dem S eine kleine Untergruppe von S_n ist. Ich frage mich, ob es möglich ist, Approximationsalgorithmen zu finden (und zu implementieren!), Die viel schneller sind als die gierigen Algorithmen (sie werden so oft ausgeführt, bis sie Glück haben), was ein sehr langsamer Vorgang ist, aber dennoch einige nahezu optimale Grenzen gesetzt hat in kleinen Fällen), oder ob Unangemessenheit garantiert, dass ich nicht kann.

Ein paar einfache Fakten zu diesem Problem: Eine zyklische Gruppe von Permutationsmatrizen der Länge n löst dieses Problem natürlich optimal. (Es werden mindestens n Matrizen benötigt, da jede Permutationsmatrix n Einsen hat und n ^ 2 Einsen benötigt werden.)

Die Mengen S, an denen ich interessiert bin, enthalten keine n-zyklische Gruppe.

Dieses Problem ist ein ganz besonderer Fall von Set-Cover. In der Tat, wenn wir X die Menge (1,2, ... n) * (1,2, ... n) mit n ^ 2 Elementen sein lassen, dann entspricht jede Permutationsmatrix einer Teilmenge der Größe n und I bin auf der Suche nach der kleinsten Teilmenge dieser Teilmengen, die X abdecken. Set-Cover selbst ist keine gute Möglichkeit, um dieses Problem zu betrachten, da eine Annäherung an das allgemeine Set-Cover-Problem besteht.

Der einzige Grund, warum dieses Problem bei Verwendung des Greedy-Ansatzes nicht viel zu langsam ist, besteht darin, dass durch Symmetrie in der Permutationsgruppe viel Redundanz beseitigt wird. Insbesondere wenn S eine Untergruppe ist und T eine kleine Untergruppe ist, die eine minimale Bedeckungsmenge ist, dann sind die Mengen sT (multiplizieren Sie T mit einem beliebigen Element der Gruppe s) immer noch in S und sind immer noch eine Bedeckungsmenge (natürlich) von gleicher Größe, also immer noch minimal.) Falls Sie sich fragen, hat der erfolgreiche Fall n ~ 30 und | S | ~ 1000, mit glücklichen gierigen Ergebnissen, die | T | haben ~ 37. Fälle mit n ~ 50 haben einige sehr schlechte Grenzen, die sehr lange dauern.

Zusammenfassend frage ich mich, ob es Annäherungsansätze für dieses Problem gibt oder ob es noch allgemein genug ist, um in einen Unannäherungstheorem zu passen, wie es es für das allgemeine Mengenabdeckungsproblem gibt. Welche Algorithmen werden verwendet, um verwandte Probleme in der Praxis zu approximieren? Es scheint, als wäre etwas möglich, da die Teilmengen alle dieselbe Größe haben und jedes Element mit derselben kleinen Frequenz 1 / n erscheint.

-B

Brayden Ware
quelle
Meinen Sie wirklich das Hinzufügen? Ich nehme an, Sie meinen stattdessen eine Art "Union" oder wirklich einen ORing? denn sonst könnten Sie mit einer 2 in einem Eintrag enden.
Suresh Venkat
Unioning funktioniert gut. Wenn ich hinzufüge, muss ich in jedem Eintrag 'mindestens' 1 bekommen. Der Grund, warum ich es mir als Addition vorstelle, ist, dass ich eigentlich Mathematiker bin und es immer noch eine mathematische Bedeutung hat, Gruppenelemente hinzuzufügen (die nicht davon abhängen, ob die Gruppe als Permutationsmatrizen dargestellt wird), aber die Matrizen nicht zu "vereinigen".
Brayden Ware
Es gibt jedoch keine sinnvolle Möglichkeit, diesen Zustand ohne die Permutationsmatrizen zu beschreiben. Denken Sie also gerne an eine Vereinigung. 2s (und Gott verbiete 3s oder mehr) würden nur als Marker dienen, dass wir nicht in der Traumlösung von genau n Matrizen sind, die zu der all 1s Matrix addieren, wobei die Anzahl von 2s und höher genau misst, wie viele zusätzliche Matrizen wir verwendet haben. (Jede zusätzliche Matrix addiert am Ende n zur Gesamtsumme.)
Brayden Ware

Antworten:

10

Hier ist eine fast enge Analyse von Approximierbarkeit für den Fall, dass S ist nicht erforderlich , um eine Untergruppe der symmetrischen Gruppe sein.

Dieses Problem ist ein Sonderfall von Set Cover, und es gibt einen einfachen Algorithmus für die gierige Approximation [Joh74]. Wenn wir die k- te Harmonische als H k = ∑ i = 1 k 1 / i bezeichnen , erreicht der Greedy-Algorithmus ein Näherungsverhältnis H n = ln n + Θ (1). (Es gibt einen Algorithmus [DF97], der zu einem etwas besseren Approximationsverhältnis H n −1/2 führt.) ( Edit : Revision 2 und früher haben angegeben, dass das Approximationsverhältnis des Greedy-Algorithmus schlechter ist als der richtige Wert.)

Darüber hinaus ist dies in folgendem Sinne nahezu optimal:

Theorem . Set Cover for Permutation Matrices können nicht innerhalb eines Approximationsverhältnisses (1 - ε ) ln n für eine Konstante 0 < ε <1 approximiert werden, es sei denn, NP NP DTIME ( n O (log log n ) ).

Hier ist eine Skizze eines Beweises. Wir schreiben [ n ] = {1,…, n }. Wir werden eine Reduktion von Set Cover konstruieren:

Cover-
Instanz festlegen : Eine positive ganze Zahl m und eine Sammlung C von Teilmengen von [ m ].
Lösung : Eine Teilmenge D von C , sodass die Vereinigung der Mengen in D gleich [ m ] ist.
Ziel : Minimieren | D |.

Es ist ein berühmtes Ergebnis von Feige [Fei98], dass Set Cover nicht innerhalb eines Näherungsverhältnisses (1 - ε ) in m für eine Konstante 0 < ε <1 approximiert werden kann, es sei denn, NP ≤ DTIME ( n O (log log n ) ).

Sei ( m , C ) eine Instanz von Set Cover. Wir werden eine Instanz ( n , S ) von Set Cover for Permutation Matrices konstruieren .

Es sei n = 2 m + 2 . Für E ⊆ [ m + 1], lassen P E die A n × n Permutationsmatrix , die mit Block diagonal sind n 2 × 2 - Blöcke , so dass i - ten Block ist wenn iE und ansonsten. Sei Q die Permutationsmatrix n × n , deren ( i , i +2) -Eintrag 1 für alle 1 ≤ in ist (wobei der Index i ist)( 1 0 0 1 )(0110)(1001)+2 werden als Modulo n ) interpretiert . Für 0 ≤ jm definieren Sie S j = { P E Q j : EC ∪ {{ m +1}}} und S = S 0 ∪… ∪ S m .

Anspruch . Lassen Sie k die Größe der Mindestdeckung von [seinen m ] in C . Dann ist die Größe der Mindestdeckung in S gleich ( k + 1) ( m + 1).

Proof-Skizze . Wenn DC eine Bedeckung von [ m ] ist, können wir eine Bedeckung TS der Größe (| D | +1) ( m +1) durch T = { P E Q j : ES ∪ {{ m +1}}, 0 ≤ jm }.

Auf der anderen Seite, lassen Sie TS eine Abdeckung sein. Es ist zu beachten, dass alle Matrizen in S 0 bei Blöcken der Größe 2 × 2 blockdiagonal sind und die anderen Matrizen in S in diesen Blöcken 0 haben. Daher deckt TS 0 diese Blöcke ab. Darüber hinaus enthält TS 0 P { m + 1}, da sonst der (2 m + 1, 2 m + 2 ) -Eintrag nicht abgedeckt würde. Beobachte, dass ( TS 0 ) ∖ { P { m +1}} Entspricht einem Satz Abdeckung in C . Daher | TS 0 | ≥ k +1. In ähnlicher Weise gilt für alle 0 ≤ jm , | TS j | ≥ k +1. Daher | T | ≥ ( k + 1) ( m + 1). Beweisendeskizze des Claim .

Gemäß Patentanspruch behält die oben konstruierte Reduktion das Näherungsverhältnis bei. Insbesondere wird der Satz aufgestellt.

Verweise

[DF97] Rong-Chii Duh und Martin Fürer. Approximation der k- set Abdeckung durch semi-lokale Optimierung. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing (STOC) , S. 256–264, Mai 1997. http://dx.doi.org/10.1145/258533.258599

[Fei98] Uriel Feige. Eine Schwelle von ln n zur Annäherung an die eingestellte Abdeckung. Journal of the ACM , 45 (4): 634–652, Juli 1998. http://dx.doi.org/10.1145/285055.285059

[Joh74] David S. Johnson. Approximationsalgorithmen für kombinatorische Probleme. Journal of Computer and System Sciences , 9 (3): 256–278, Dezember 1974. http://dx.doi.org/10.1016/S0022-0000(74)80044-9

Tsuyoshi Ito
quelle
3
Tsuyoshi, Ihre Antworten in letzter Zeit waren ziemlich beeindruckend. Eines Tages wird einer Ihrer Beweise auf dieser Site als Ito Lemma bezeichnet. :-)
Aaron Sterling
@ Aaron: Danke für deinen freundlichen Kommentar. Beachten Sie, dass das Schwierigste in der Frage, nämlich die Beschränkung auf den Fall einer Untergruppe, in dieser Antwort völlig ignoriert wird. Es ist Zeit zum Nachdenken!
Tsuyoshi Ito
3
@ Aaron: Ich weiß nicht, ob Sie das absichtlich gesagt haben, aber Itos Lemma ist genommen ( en.wikipedia.org/wiki/Ito_lemma ).
Robin Kothari
11

Beim Mittagessen in Brüssel haben wir bewiesen, dass dieses Problem NP-schwer ist, und zwar durch eine relativ kurze Reduzierung von 3SAT. Unser Beweis führt (noch) nicht zu einem unangemessenen Ergebnis. Wir werden mehr darüber nachdenken.

In etwa transformieren Sie eine 3-SAT-Instanz (mit n Variablen und c-Klauseln) in eine Reihe von Permutationen, die wie folgt aufgebaut sind:

1 ... n zum Nummerieren der n Variablen n + 1, die vom Variablen-Gadget n + 2 verwendet werden, wobei n + 3 die 1. Klausel darstellt ... n + 2j, n + 2j + 1 die j-te Klausel n + 2c + 2 darstellt vom Müllmann benutzt

Die Variable xi wird durch die Permutation 1, ..., i-1, n + 1, i + 1, ..., n, i, ... und Vertauschen von n + 2j + 1, n + 2j für jede Klausel dargestellt wo j wo xi erscheint; und die Permutation 1, ..., i-1, n + 1, i + 1, ..., n, i, ... und Vertauschen von n + 2j + 1, n + 2j für jeden Satz, in dem j wo - xi erscheint.

Dann verwenden wir den Garbage Collector, um jede Zahl an einer Position zu platzieren, an der sie sonst nicht erscheinen könnte. Um x in Position y zu setzen, setzen wir y in Position n + 2c + 2 und n + 2c + 2 in Position x. Wir werden genau n + 2c-1 solcher Garbage Collectors für jede Variable und 2 (n + 2c-1) für jede Klausel haben. Der 3SAT ist erfüllbar, wenn wir für jede Variable genau eine der 2 Permutationen wählen können, wenn die Permutationsmenge eine Lösung der Größe n + (n + 2c-1) (n + 2c) hat.

Für kleine Fälle fehlen wahrscheinlich einige kleinere Details.

Stefan.

Stefan Langerman
quelle