Znaczenie luki w integralności

Zawsze miałem problem ze zrozumieniem znaczenia luki integralności (IG) i ją ograniczam. IG jest stosunkiem (jakości) optymalnej liczby całkowitej do (jakości) optymalnego rzeczywistego rozwiązania złagodzenia problemu. Rozważmy przykrycie wierzchołków (VC) jako przykład. VC można określić jako znalezienie optymalnego rozwiązania liczb całkowitych następującego zestawu równań liniowych:

Mamy zero / jednego o wartości zmiennych $x_v$ s dla każdego wierzchołka $v \in V(G)$ na wykresie $G$ . Równania to: dla i dla każdej krawędzi . Szukamy wartości, które zminimalizują .v ∈ V ( G ) 1 ≤ x v + x u u v ∈ E ( G ) ∑ v ∈ V ( G ) x $0 \leq x_v \leq 1$$v\in V(G)$$1 \leq x_v+x_u$$uv \in E(G)$$\sum_{v \in V(G)} x_v$

Złagodzenie tego problemu pozwala na uzyskanie rzeczywistych wartości od do więc przestrzeń rozwiązań jest większa, a optymalne rzeczywiste rozwiązanie może być mniejsze niż optymalne rozwiązanie liczb całkowitych, które chcemy znaleźć. Dlatego musimy znaleźć proces „zaokrąglania” optymalnej rzeczywistej odpowiedzi uzyskanej z programowania liniowego, aby znaleźć rozwiązanie liczb całkowitych. Optymalne rozwiązanie liczb całkowitych będzie znajdować się między optymalnym rozwiązaniem rzeczywistym a wynikiem procesu zaokrąglania. IG jest stosunkiem optymalnego rozwiązania liczby całkowitej do optymalnego rozwiązania rzeczywistego i nie mówi nic o procesie zaokrąglania. Proces zaokrąglania może (teoretycznie) całkowicie zignorować rzeczywiste rozwiązanie i bezpośrednio obliczyć optymalne rozwiązanie liczb całkowitych.$0$$1$

Dlaczego ludzie są zainteresowani udowodnieniem granic na IG?

Luki integralności zasadniczo reprezentują granice nieodłącznego określonego relaksacji liniowej lub wypukłej w przybliżeniu programu liczb całkowitych. Zasadniczo, jeśli luka integralności danego relaksacji wynosi , to żaden algorytm aproksymacji oparty na tej relaksacji nie może mieć nadziei na lepsze wyniki niż aproksymacja x . Zatem przynajmniej luki w integralności są interesujące dla projektantów algorytmów, ponieważ sugerują ograniczenia w niektórych technikach. $x$$x$

Dlaczego więc nie wymyślić kolejnej relaksacji LP lub przejść na inne techniki i przejść dalej? Programowanie liniowe i wypukłe okazało się kluczowe dla algorytmów aproksymacyjnych; w przypadku wielu problemów luka integralności naturalnego sformułowania LP lub SDP jest równa współczynnikowi przybliżenia najlepszego algorytmu, jak również twardości współczynnika przybliżenia. Jest to tylko obserwacja empiryczna, ale oznacza, że ​​wykazanie luki integralności może sugerować znacznie silniejsze konsekwencje ulepszonego algorytmu lub dolnej granicy.

Przyczyny tego zjawiska mogą być głębsze i bardziej rygorystyczne. Na przykład, zakładając unikalną hipotezę gier, wiadomo, że współczynnik aproksymacji i współczynnik niedopuszczalności dla problemów satysfakcji z ograniczeń jest równy luce integralności prostej relaksacji SDP (patrz: Optymalne algorytmy i wyniki niedopuszczalności dla każdego CSP? Prasad Raghavendra)

Wreszcie luki w integralności reprezentują bezwarunkowe dolne granice. Zwykle musimy polegać na niepotwierdzonych założeniach (np. ), jeśli chcemy poczynić jakiekolwiek postępy w dolnych granicach, ale w przypadku ograniczonych modeli obliczeń możemy czasem uciec bez niego (patrz uwagi do wykładu Lucy Trevisana). Luki w integralności, będące czysto geometryczne, a nie obliczeniowe, są jednym ze sposobów uzyskania dość potężnych dolnych granic bez bagażu dodatkowych założeń.$P \neq NP$

Załóżmy, że Twój problem zainteresowania jest problemem minimalizacji i które rozwinęły algorytm -approximate. Jeśli na danym wejściu algorytm generuje rozwiązanie kosztu c , wówczas obliczenie algorytmu wraz z jego analizą daje certyfikat, że na tym wejściu optymalne jest co najmniej a / c . Oczywiście, a jest co najmniej optymalne, więc dla każdego wkładu jesteśmy w stanie poświadczyć dolną granicę optimum, która stanowi co najmniej 1 / c ułamek samego optimum.$a$$c$$a/c$$a$$1/c$

We wszystkich algorytmach opartych na wypukłych (LP i SDP) relaksacjach, o których jestem świadomy, poświadczone dolne ograniczenie do optimum jest określone przez optimum relaksacji. Jeśli relaksacja ma lukę integralności , wówczas nie będzie możliwe osiągnięcie lepszego współczynnika aproksymacji niż ja , chyba że w analizie wprowadzono technikę ograniczenia dolnego dla optimum, która jest silniejsza niż dolna granica zapewniana przez relaksację.$I$$I$

Luka integralności jest użytecznym wskaźnikiem tego, jak dobrze można oszacować IP. Lepiej byłoby myśleć o tym w nieformalny, intuicyjny sposób. Duża luka w integralności oznacza, że ​​niektóre metody nie będą działać. Na przykład niektóre metody pierwotne / podwójne zależą od małej luki integralności. W przypadku standardowej pierwotnej osłony wierzchołków LP podwójny LP wymaga maksymalnego dopasowania. W takim przypadku możemy wykonać następujące czynności:

• $\boldsymbol{y}$
• $\boldsymbol{y}$
• $\boldsymbol{x}$$2\boldsymbol{y}$$\boldsymbol{x}$$x_i$$\min(\lfloor x_i\rfloor, 1)$

W tym przypadku ta prosta strategia działa i uzyskujemy możliwe integralne rozwiązanie dla pierwotnego LP, którego waga jest nie więcej niż dwa razy większa niż wykonalne rozwiązanie dla podwójnego LP. Ponieważ waga wykonalnego rozwiązania dla podwójnego LP jest dolną granicą dla OPT, jest to algorytm 2-aproksymacyjny.

Gdzie zatem pojawia się luka w integralności? IG ma w tym przypadku 2, ale samo to nie oznacza, że ​​algorytm będzie działał. Raczej sugeruje, że może działać. A jeśli IG miałby więcej niż 2, gwarantowałoby to, że prosta strategia nie zawsze działałaby. Musielibyśmy przynajmniej pomnożyć podwójne rozwiązanie przez IG. Luka integralności czasami mówi nam, co nie zadziała. Luka integralności może również wskazywać, jakiego rodzaju współczynnika przybliżenia możemy się spodziewać. Mała luka integralności sugeruje, że badanie strategii zaokrąglania itp. Może być opłacalnym podejściem.

Aby uzyskać bardziej interesujący przykład, rozważ problem Zestaw uderzeń i potężną technikę przybliżania problemu za pomocą -nets (Brönnimann i Goodrich, 1995) . Wiele problemów można sformułować jako przykłady zestawu uderzeń, a strategią, która odniosła sukces w przypadku wielu problemów, jest zrobienie tego, a następnie po prostu znalezienie dobrej wyszukiwarki sieci, tj. Algorytmu do budowy małych sieci i przekręcenia wszystkiego przez meta-algorytm B&G. Tak więc ludzie (w tym ja) próbują znaleźć wyszukiwarki sieci dla ograniczonych instancji zestawu uderzeń, które dla każdego mogą zbudować -net o rozmiarze , gdzie funkcja$\varepsilon$$\varepsilon$$\varepsilon$$\varepsilon$$f(1/\varepsilon)$$f$powinien być jak najmniejszy. Posiadanie jest typowym celem; dałoby to .$f(1/\varepsilon) = \mathcal{O}(1/\varepsilon)$$\mathcal{O}(1)$

Jak się okazuje, najlepszą możliwą funkcją jest luka integralności pewnego LP dla zestawu uderzającego (Even, Rawitz, Shahar, 2005) . W szczególności optymalne rozwiązania integralne i ułamkowe spełniają . W przypadku nieograniczonych przypadków Uderzenia Zestawem luki integralności jest , ale przy formułowaniu innego problemu jako Uderzenie Zestawem IG może być niższy. W tym przykładzie autorzy pokazują, jak znaleźć sieci o rozmiarze$f$$\mathrm{OPT}_I \leq f(\mathrm{OPT}_f)$$\Theta(\log(m))$$\varepsilon$$\mathcal{O}((1/\varepsilon) \log \log (1/\varepsilon))$dla ograniczonych przypadków Uderzenia Zestawu, które odpowiadają problemowi uderzenia w równoległe pola osi. W ten sposób poprawiają najbardziej znany współczynnik przybliżenia tego problemu. Problemem otwartym jest to, czy można to poprawić. Jeśli dla tych ograniczonych instancji zestawu uderzeń IG dla zestawu uderzeń LP to , niemożliwe byłoby zaprojektowanie wyszukiwarki sieci gwarantującej sieci o rozmiarze , ponieważ oznaczałoby to istnienie algorytmu, który gwarantuje integralne uderzanie zbiorów o rozmiarze , ale od$\Theta(\log \log m)$$\varepsilon$$o((1/\varepsilon) \log \log (1/\varepsilon))$$o(\mathrm{OPT}_f \log\log \mathrm{OPT}_f)$$\mathrm{OPT}_f\leq m$oznaczałoby to mniejszą lukę integralności. Jeśli więc różnica w integralności jest duża, udowadniając, że może to uniemożliwić ludziom marnowanie czasu na szukanie dobrych wyszukiwarek.

Gdy wymyślisz algorytm aproksymacyjny dla jakiegoś problemu maksymalizacji NP-trudnego, możesz zwrócić uwagę na kilka wartości: Istnieje OPT, optymalna wartość twojego problemu, która jest taka sama jak OPT (IP), optymalna wartość każdego poprawnego sformułowania IP twojego problemu. Istnieje również OPT (LP), optymalna wartość liniowej relaksacji twojego adresu IP.

$OPT(LP) \geq OPT(IP)$

Wreszcie jest V, wartość rozwiązania, które otrzymujesz zaokrąglając rozwiązanie LP. Chcesz być w stanie udowodnić, że , aby pokazać, że algorytm jest przybliżenie, ale często nie jest to możliwe, aby to zrobić bezpośrednio, ponieważ nie mają przytrzymaj przestrzeń rozwiązania. Zamiast tego prawie zawsze udowodniono, że . To oczywiście implikuje , ale jest silniejsze. W szczególności, jeśli luka integralności formuły IP jest większa niż , powyższe stwierdzenie będzie ogólnie fałszywe, ponieważ procedura zaokrąglania kończy się rozwiązaniem integralnym.$V > \frac{OPT(IP)}{c}$$c$$V \geq \frac{OPT(LP)}{c}$$V > \frac{OPT(IP)}{c}$$c$

Więc sedno jest takie: LP daje rozwiązanie, o którym wiesz, że jest „dobre” i chcesz zaokrąglić to do czegoś, co jest „prawie tak dobre”. Jeśli różnica w integralności jest duża, jest to na ogół niemożliwe, ponieważ nigdy nie będzie procedury, która zagwarantuje uzyskanie rozwiązania integralnego, które byłoby „tak dobre” jak rozwiązanie LP - ponieważ czasami takie nie istnieją!

Masz rację, ponieważ luka integralności relaksacji jako taka nie ma nic wspólnego z żadnym algorytmem zaokrąglania. To są dwa różne pojęcia. Luka integralności jest właściwością określonego relaksu. To znaczy, o ile większa jest wartość tego rozluźnienia w porównaniu z optymalną wartością całkowitą?

Dlaczego dbamy o relaksacje liniowe / wypukłe? Aby skutecznie przybliżyć wartość całkowitą. Dlatego zwykle mówimy o relaksacjach tylko w przypadkach, gdy trudno jest obliczyć optymalną wartość i jesteśmy zainteresowani wydajnymi przybliżeniami. Luki w integralności pokazują nam nieodłączne ograniczenia tego, co można osiągnąć dzięki takim technikom.

Więc, dlaczego dbamy o zaokrąglenie algorytmów na górze relaksu? Używamy algorytmów zaokrąglania do rozwiązania problemu algorytmicznego znalezienia rozwiązania prawie optymalnego, a nie tylko przybliżenia wartości rozwiązania optymalnego. Ponadto często stosuje się algorytmy zaokrąglania w celu ograniczenia luki integralności relaksacji.

Technicznie rzecz biorąc, luka integralności dotyczy konkretnego sformułowania IP, a nie (jak to sformułowałeś) stosunku między najlepszym relaksacją liniową a optymalnym rozwiązaniem (które wydaje się kwantyfikować w odniesieniu do WSZYSTKICH sformułowań IP).

$c$$c$

Był bardzo interesujący artykuł „O zaletach kodowania sieciowego w celu poprawy przepustowości sieci”, który wykazał, że luka integralności „dwukierunkowego rozluźnienia cięcia” dla problemu drzewa Steiner'a dokładnie odpowiada rodzajowi „korzyści kodowania” w komunikacji sieciowej. Nie znam wielu innych podobnych artykułów. Jednak należy również zauważyć, że pozornie lepsze relaksacje LP dla problemu drzewa Steinera są znane (np. Patrz nowy algorytm aproksymacji aproksymacyjnej oparty na LP autorstwa Byrka i in. W STOC 2010, również bezwstydnie zgłaszam się do współautora kilku ostatnich prac poświęconych hipergraphicowi LP).

Większość odpowiedzi dotyczyła już głównego powodu, dla którego należy dbać o lukę integralności, a mianowicie, że algorytm aproksymacyjny oparty wyłącznie na wykorzystaniu granicy zapewnionej przez relaksację nie może mieć nadziei na udowodnienie stosunku lepszego niż luka integralności. Podam jeszcze dwa inne powody, dla których luka integralności jest użytecznym przewodnikiem. W przypadku dużej klasy problemów optymalizacji kombinatorycznej równoważność separacji i optymalizacji pokazuje, że dokładne algorytmy są ściśle związane z wypukłym kadłubem wykonalnych rozwiązań problemu. W ten sposób perspektywa geometryczna i algorytmiczna są ze sobą ściśle powiązane. Podobna formalna równoważność nie jest znana algorytmom aproksymacyjnym, ale jest to przydatny przewodnik - algorytmy idą w parze z relaksacjami geometrycznymi. Innowacje algorytmiczne mają miejsce, gdy ludzie mają konkretny cel do poprawy.