Deckung für Permutationsmatrizen festlegen

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

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 i ∈ E und ansonsten. Sei Q die Permutationsmatrix n × n , deren ( i , i +2) -Eintrag 1 für alle 1 ≤ i ≤ n ist (wobei der Index i ist)( 1 0 0 1$\pmatrix{0 & 1 \\ 1 & 0}$$\pmatrix{1 & 0 \\ 0 & 1}$+2 werden als Modulo n ) interpretiert . Für 0 ≤ j ≤ m definieren Sie S _j = { P _E Q ^j : E ∈ C ∪ {{ m +1}}} und S = S ₀ ∪… ∪ 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 D ⊆ C eine Bedeckung von [ m ] ist, können wir eine Bedeckung T ⊆ S der Größe (| D | +1) ( m +1) durch T = { P _E Q ^j : E ∈ S ∪ {{ m +1}}, 0 ≤ j ≤ m }.

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

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.