Ustaw osłonę dla macierzy permutacyjnych

17

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

Brayden Ware
źródło
czy naprawdę masz na myśli dodawanie? Zakładam, że masz na myśli rodzaj „unii”, czy naprawdę ORing? ponieważ w przeciwnym razie możesz otrzymać 2 we wpisie.
Suresh Venkat
Łączenie działa dobrze. Jeśli dodam, muszę uzyskać „co najmniej” 1 w każdym wpisie. Powodem, dla którego wyobrażam sobie, że jest dodawanie, jest to, że tak naprawdę jestem matematykiem, a dodawanie elementów grupy wciąż ma matematyczne znaczenie (które nie zależy od reprezentacji grupy jako macierzy permutacji), ale nie w „łączeniu” macierzy.
Brayden Ware,
Ale nie ma żadnego użytecznego sposobu stwierdzenia tego stanu bez matryc permutacyjnych, więc możesz pomyśleć o zjednoczeniu. 2s (i chrońmy 3s lub więcej) służyłyby jedynie jako markery, że nie jesteśmy w wymarzonym rozwiązaniu dokładnie n macierzy dodających do macierzy wszystkich 1s, liczby 2s i więcej, mierząc ile dodatkowych macierzy użyliśmy. (Każda dodatkowa macierz dodaje n do całkowitej sumy na końcu.)
Brayden Ware,

Odpowiedzi:

10

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(0110)jeśli iE i(1001)Inaczej. Niech Q będzie macierzą permutacji n × n , której wpis ( i , i +2) wynosi 1 dla wszystkich 1in (gdzie indeks i +2 są interpretowane jako modulo n ). Dla 0 ≤ jm zdefiniuj S j = { P E Q j : EC ∪ {{ m +1}}} i S = S 0 ∪… ∪ 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 DC jest przykryciem [ m ], możemy skonstruować przykrycie TS o rozmiarze (| D | +1) ( m +1) przez T = { P E Q j : ES ∪ {{ m +1}}, 0 ≤ jm }.

Z drugiej strony, niech TS będzie przykrywką. Zauważ, że wszystkie macierze w S 0 są blokami ukośnymi z blokami o rozmiarze 2 × 2, a inne macierze w S mają 0 w tych blokach. Dlatego TS 0 obejmuje te bloki. Co więcej, TS 0 zawiera P { m +1}, ponieważ w przeciwnym razie (2 m +1, 2 m +2) wpis nie zostałby objęty. Zauważ, że ( TS 0 ) ∖ { P { m +1} } odpowiada ustawionemu pokryciu w C . Dlatego | T S 0 | ≥ k +1. Podobnie, dla każdego 0 ≤ jm , | TS 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

Tsuyoshi Ito
źródło
3
Tsuyoshi, twoje odpowiedzi były ostatnio imponujące. Pewnego dnia jeden z twoich dowodów na tej stronie będzie cytowany jako Ito Lemma. :-)
Aaron Sterling
@Aaron: Dziękuję za miły komentarz. Zauważ, że najtrudniejsza rzecz w pytaniu, a mianowicie ograniczenie do podgrupy, jest całkowicie ignorowana w tej odpowiedzi. Czas pomyśleć!
Tsuyoshi Ito,
3
@Aaron: Nie wiem, czy powiedziałeś to celowo, ale lemat Ito jest zajęty ( en.wikipedia.org/wiki/Ito_lemma ).
Robin Kothari,
11

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.

Stefan Langerman
źródło