Ustaw osłonę dla macierzy permutacyjnych

Biorąc pod uwagę zestaw S macierzy permutacji nxn (który jest tylko małą częścią n! Możliwych macierzy permutacji), w jaki sposób możemy znaleźć podzbiory T o minimalnej wielkości, tak że dodanie macierzy T ma co najmniej 1 w każdej pozycji?

Interesuje mnie ten problem, w którym S jest małą podgrupą S_n. Zastanawiam się, czy można znaleźć (i zaimplementować!) Algorytmy aproksymacyjne, które są znacznie szybsze niż algorytmy zachłanne (uruchamiane wiele razy, aż osiągną „szczęście”, co jest bardzo powolną procedurą, ale mimo to dało pewne bliskie optymalne granice w małych przypadkach), lub czy niedopuszczalność gwarantuje, że nie mogę.

Kilka prostych faktów na temat tego problemu: Długość n cyklicznej grupy matryc permutacyjnych rozwiązuje ten problem, oczywiście optymalnie. (Potrzebnych jest co najmniej n macierzy, ponieważ każda macierz permutacji ma n jednych i potrzebnych jest n ^ 2).

Zbiory S, których jestem zainteresowany, nie mają w sobie grupy n-cyklicznej.

Ten problem jest bardzo szczególnym przypadkiem pokrycia zestawu. Rzeczywiście, jeśli pozwolimy X być zbiorem (1,2, ... n) * (1,2, ... n), z elementami n ^ 2, to każda macierz permutacji odpowiada podzbiorowi rozmiaru n, a I szukam najmniejszej podkolekcji tych podzbiorów, które obejmują X. Sama okładka zestawu nie jest dobrym sposobem na przyjrzenie się temu problemowi, ponieważ jest to przybliżenie ogólnego problemu z pokrywą zestawu.

Jedynym powodem, dla którego ten problem nie jest zbyt wolny w przypadku chciwego podejścia, jest to, że symetria w grupie permutacji pomaga wyeliminować wiele nadmiarowości. W szczególności, jeśli S jest podgrupą, a T jest małym podzbiorem, który jest minimalnym zestawem obejmującym, wówczas zestawy sT (pomnóż T przez dowolny element grupy) są nadal w S i nadal są zestawem obejmującym (oczywiście tego samego rozmiaru, więc wciąż minimalny.) Jeśli się zastanawiasz, pomyślna skrzynka ma n ~ 30 i | S | ~ 1000, a szczęście, że chciwe wyniki mają | T | ~ 37. Przypadki z n ~ 50 mają bardzo słabe granice, których uzyskanie zajmuje bardzo dużo czasu.

Podsumowując, zastanawiam się, czy istnieją podejścia przybliżające do tego problemu, czy też jest ono na tyle ogólne, że mieści się w jakimś twierdzeniu o niedopuszczalności - podobnie jak w przypadku ogólnego problemu pokrycia zestawu. Jakie algorytmy są stosowane w celu przybliżenia powiązanych problemów w praktyce? Wydaje się, że może istnieć coś możliwego, ponieważ wszystkie podzbiory są tego samego rozmiaru, a każdy element pojawia się na tej samej małej częstotliwości 1 / n.

-B

Tutaj jest prawie szczelne approximability analizę dla przypadku, w którym S jest nie wymaga się podgrupę grupy symetryczny.

Ten problem jest szczególnym przypadkiem Set Cover i istnieje prosty, zachłanny algorytm aproksymacji [Joh74]. Jeśli oznaczymy k th liczby harmonicznych H _k = Ď _{I = 1} ^K 1 / I , algorytm chciwy osiąga przybliżenie współczynnika H _n = ln n + Θ (1). (Istnieje algorytm [DF97], który powoduje nieco lepszy współczynnik aproksymacji H _n −1/2.) ( Edycja : Wersja 2 i wcześniejsze podały, że stosunek aproksymacji algorytmu zachłannego jest gorszy niż poprawna wartość.)

Co więcej, jest to prawie optymalne w następującym znaczeniu:

Twierdzenie . Ustawienie Pokrycia dla macierzy permutacji nie może być aproksymowane w ramach stosunku aproksymacji (1 ε ) ln n dla dowolnej stałej 0 < ε <1, chyba że NP ⊆ DTIME ( n ^{O (log log n )} ).

Oto szkic dowodu. Piszemy [ n ] = {1,…, n }. Zbudujemy redukcję z Zestawu okładki:

Ustaw
wystąpienie okładki : dodatnia liczba całkowita mi zbiór C podzbiorów [ m ].
Rozwiązanie : Podzbiór D z C taki, że suma zbiorów w D jest równa [ m ].
Cel : minimalizacja | D |.

Jest to znany wynik Feige [Fei98], że Set Cover nie może być aproksymowany w ramach stosunku aproksymacji (1 ε ) ln m dla dowolnej stałej 0 < ε <1, chyba że NP ⊆ DTIME ( n ^{O (log log n )} ).

Niech ( m , C ) będzie instancją Set Cover. Zbudujemy instancję ( n , S ) zestawu Cover for Permutation Matrices.

Niech n = 2 m + 2. Dla E ⊆ [ m + 1], niech P _E jest n x n macierzy permutacji, który jest blok przekątnej z n 2 x 2 bloki tak, że i tego bloku jest$\pmatrix{0 & 1 \\ 1 & 0}$jeśli i ∈ E i$\pmatrix{1 & 0 \\ 0 & 1}$Inaczej. Niech Q będzie macierzą permutacji n × n , której wpis ( i , i +2) wynosi 1 dla wszystkich 1 ≤ i ≤ n (gdzie indeks i +2 są interpretowane jako modulo n ). Dla 0 ≤ j ≤ m zdefiniuj S _j = { P _E Q ^j : E ∈ C ∪ {{ m +1}}} i S = S ₀ ∪… ∪ S _m .

Roszczenie . Niech K będzie rozmiarem minimalnym osłoną [ m ] w C . Zatem rozmiar minimalnej osłony w S jest równy ( k +1) ( m +1).

Szkic próbny . Jeśli D ⊆ C jest przykryciem [ m ], możemy skonstruować przykrycie T ⊆ S o rozmiarze (| D | +1) ( m +1) przez T = { P _E Q ^j : E ∈ S ∪ {{ m +1}}, 0 ≤ j ≤ m }.

Z drugiej strony, niech T ⊆ S będzie przykrywką. Zauważ, że wszystkie macierze w S ₀ są blokami ukośnymi z blokami o rozmiarze 2 × 2, a inne macierze w S mają 0 w tych blokach. Dlatego T ∩ S ₀ obejmuje te bloki. Co więcej, T ∩ S ₀ zawiera P _{{ m +1},} ponieważ w przeciwnym razie (2 m +1, 2 m +2) wpis nie zostałby objęty. Zauważ, że ( T ∩ S ₀ ) ∖ { P _{{ m +1}} } odpowiada ustawionemu pokryciu w C . Dlatego | T ∩ S ₀ | ≥ k +1. Podobnie, dla każdego 0 ≤ j ≤ m , | T ∩ S _j | ≥ k +1. Dlatego | T | ≥ ( k +1) ( m +1). Koniec szkicu dowodu roszczenia .

Według zastrzeżenia skonstruowana powyżej redukcja zachowuje stosunek przybliżenia. W szczególności ustanawia to twierdzenie.

Bibliografia

[DF97] Rong-Chii Duh i Martin Fürer. Przybliżenie pokrycia zestawu K przez pół-lokalną optymalizację. W Proceedings of dwudziestego dziewiątego rocznego ACM Symposium on Theory of Computing (stoc) , str. 256-264, maj 1997. http://dx.doi.org/10.1145/258533.258599

[Fei98] Uriel Feige. Próg ln n dla przybliżenia zestawu osłon. Journal of the ACM , 45 (4): 634–652, lipiec 1998. http://dx.doi.org/10.1145/285055.285059

[Joh74] David S. Johnson. Algorytmy aproksymacyjne dla problemów kombinatorycznych. Journal of Computer and System Sciences , 9 (3): 256–278, grudzień 1974. http://dx.doi.org/10.1016/S0022-0000(74)80044-9

Podczas lunchu w Brukseli udowodniliśmy, że ten problem jest trudny do uniknięcia dzięki dość krótkiej redukcji z 3SAT. Nasz dowód nie prowadzi (jak dotąd) do skutku niedopuszczalności. Zastanowimy się nad tym więcej.

Z grubsza transformujesz instancję 3-SAT (z n zmiennymi i klauzulami c) w serię permutacji o następującej strukturze:

1 ... n do numerowania n zmiennych n + 1 używanych przez gadżet zmiennej n + 2, n + 3 reprezentujących 1. klauzulę ... n + 2j, n + 2j + 1 reprezentujących j. Klauzulę n + 2c + 2 używany przez śmieciarza

zmienna xi jest reprezentowana przez permutację 1, ..., i-1, n + 1, i + 1, ..., n, i, ... i zamiana n + 2j + 1, n + 2j dla każdej klauzuli gdzie j gdzie pojawia się xi; i permutacja 1, ..., i-1, n + 1, i + 1, ..., n, i, ... i zamiana n + 2j + 1, n + 2j dla każdej klauzuli, gdzie j gdzie - pojawia się xi.

Następnie używamy śmietnika do umieszczenia każdego numeru w pozycji, w której inaczej by się nie pojawił. Aby umieścić x w pozycji y, umieszczamy y w pozycji n + 2c + 2 oraz n + 2c + 2 w pozycji x. Będziemy mieli dokładnie n + 2c-1 takich śmieciarek dla każdej zmiennej i 2 (n + 2c-1) dla każdej klauzuli. 3SAT jest zadowalający, jeśli możemy wybrać dokładnie jedną z 2 permutacji dla każdej zmiennej, i jeśli pokrywa zestawu permutacji ma rozwiązanie o rozmiarze n + (n + 2c-1) (n + 2c).

Prawdopodobnie brakuje drobnych szczegółów dla małych instancji.

Stefan.