Luka integralności i współczynnik aproksymacji

Gdy weźmiemy pod uwagę algorytm aproksymacji dla problemu minimalizacji, luka integralności formuły IP dla tego problemu daje dolną granicę współczynnika aproksymacji dla pewnej klasy algorytmów (takich jak algorytm zaokrąglania lub pierwotny podwójny). W rzeczywistości istnieje wiele problemów, których najlepszy współczynnik aproksymacji odpowiada luce integralności.

Niektóre algorytmy mogą mieć lepszy współczynnik aproksymacji niż luka integralności dla jakiegoś problemu, ale nie wiem, czy taki przykład istnieje, czy nie. Jeśli odpowiedź brzmi tak, czy możesz podać kilka przykładów?

Wiem, że niektóre problemy dopuszczają wiele formuł matematycznych. W takich przypadkach rozważ formułę matematyczną z najmniejszą luką integralności, o ile można ją rozwiązać w czasie wielomianowym (być może niektóre formulacje mogą używać wyroczni rozdzielających).

To pytanie dotyczy [pytania: Znaczenie luki w integralności] .

ds.algorithms approximation-algorithms linear-programming integrality-gap Snowie
źródło

Sądzę, że geometryczny TSP byłby przykładem takiego problemu, ale nie mam żadnych odniesień.

Jukka Suomela

A co z problemami, które dopuszczają PTAS przy użyciu strategii zmiany biegów? Czy któryś z nich ma sformułowanie IP z dowolnie małą luką integralności?

Jukka Suomela

@Jukka geometryczny TSP jest dobrym przykładem. Przykład luki integralności 4/3 to metryka najkrótszej ścieżki na wykresie planarnym i powinna istnieć możliwość przekształcenia się w instancję Euclidean TSP lub TSP w płaszczyźnie z luką

ℓ_{1}

$\ell_1$

1 + ϵ

$1+\epsilon$

Luca Trevisan

Słyszałem, że wspomniano o tym jako ciekawym otwartym pytaniu, czy PTAS dla problemów na grafach płaskich można zrealizować przy użyciu stałej liczby poziomów relaksacji Sherali-Adamsa lub Lasserre. (Gdzie stała zależy od proporcji aproksymacji, którą chce się osiągnąć.) Należy wiedzieć, a przynajmniej udowodnić za pomocą obecnych technik, że problemy z grafem, które mają PTAS na gęstych grafach (np. Maksymalne cięcie), również mają rodzinę wielomianów rozluźnienia wielkości z dowolnie małymi lukami integralności.

Luca Trevisan

Powiązane pytanie: Czy istnieje jakikolwiek problem, który został udowodniony, że jakikolwiek LP wielomianowy nie może podać obecnie najlepiej znanego współczynnika aproksymacji? Czy można to udowodnić, nawet w przypadku niektórych ograniczonych rodzajów płyt LP?

Danu

Odpowiedzi:

Jak wskazano, istnieje wiele przykładów.

Klasycznym przykładem jest maksymalne dopasowanie, w którym relaksacja „naturalna” (bez ograniczeń nieparzystych) ma przerwę 2, podczas gdy istnieje oczywiście wydajny algorytm. Ten nie kwalifikuje się jednak w pełni, ponieważ istnieje wykładniczy rozmiar LP, który można rozwiązać za pomocą elipsoidy.

Intrygującą jest pojemna lokalizacja obiektu. Tutaj naturalny relaks ma nieograniczoną lukę integralności. Jednak lokalne algorytmy wyszukiwania dają stałe przybliżenia współczynników.

Innym bardzo interesującym (choć jest to problem maksymalizacji) jest ten artykuł: http://www.cis.upenn.edu/~sanjeev/postscript/FOCS09_MaxMin.pdf . Tutaj LP ma dużą lukę, a jednak algorytm, który używa tego LP, może zrobić lepiej.

Kunal
źródło

Dziękuję Ci bardzo. Ta odpowiedź zawiera to, czego szukałem, zwłaszcza artykuł FOCS napisany przez Chakrabarty i in. (ten artykuł bardzo mnie interesuje). Dlatego ustawiam tę odpowiedź jako przyjętą. Nadal szukam więcej przykładów, więc każdy, kto może podać inne przykłady, byłby bardzo wdzięczny.

Snowie

Istnieją różne przykłady, w których relaksacja programowania półfinałowego pozwala na aproksymację przewyższającą znane luki integralności dla relaksacji programowania liniowego.

Na przykład standardowe rozluźnienie programowania liniowego maksymalnego cięcia ma lukę integralności równą 1/2, i jest to prawdą nawet w przypadku znacznie bardziej wyrafinowanych rozluźnień programowania liniowego (por. De la Vega-Kenyon i Schoenebeck-Trevisan-Tulsiani), ale Goemans Algorytm Williamson SDP ma przybliżenie. 878 ...

Relaksacja programowania liniowego Leighton-Rao dla najrzadszego cięcia ma lukę integralności , ale algorytm Arora-Rao-Vazirani SDP ma aproksymację . $\Omega(\log n)$ $O(\sqrt{\log n})$

Być może mniej znane, Karloff i Zwick pokazują, że za pomocą SDP można uzyskać przybliżenie Max 3SAT, w wersji, w której klauzule mogą mieć 1, 2 lub 3 literały, w granicach 7/8, podczas gdy Goemans i Williamson badali relaksację programowania liniowego, którą oni używane do udowodnienia przybliżenia 3/4 (Yannakakis wcześniej podał przybliżenie 3/4 innymi metodami), a relaksacja LP Goemansa-Williamsona dla Max 3SAT jest łatwa do zauważenia, że ma lukę integralności 3/4.

Luca Trevisan
źródło

Jest także wynik Granta w rozwiązywaniu układów liniowych za pomocą GF_2. W przypadku układów równań z dobrym rozwiązaniem masz lukę integralności SDP (w bardzo silnej formie) wynoszącą 2, podczas gdy możesz użyć Eliminacji Gaussa, aby dokładnie rozwiązać problem.

YI WU
źródło