Twardość aproksymacji - błąd addytywny

24

Istnieje bogata literatura i co najmniej jedna bardzo dobra książka określająca znaną twardość wyników przybliżenia dla problemów trudnych dla NP w kontekście błędu multiplikatywnego (np. 2-przybliżenie dla pokrywy wierzchołków jest optymalne przy założeniu UGC). Obejmuje to również dobrze zrozumiałe klasy złożoności aproksymacji, takie jak APX, PTAS i tak dalej.

Co wiadomo, kiedy należy uwzględnić błąd addytywny? Wyszukiwanie w literaturze pokazuje kilka wyników typu górnego limitu, w szczególności dla pakowania pojemników (patrz na przykład http://www.cs.princeton.edu/courses/archive/spr03/cs594/dpw/lecture2.ps ), ale tam jest bardziej kompleksowa klasyfikacja klas złożoności czy istnieje powód, dla którego nie jest ona tak interesująca ani istotna?

Jako kolejny komentarz, na przykład w przypadku pakowania pojemników, nie ma teoretycznego powodu, dla którego nie można znaleźć algorytmu wieloczasowego, który zawsze znajduje się w odległości addytywnej od optymalnej wartości 1 (chociaż mogę to poprawić ). Czy taki algorytm zawaliłby jakiekolwiek klasy złożoności lub miałby jakikolwiek inny istotny teoretyczny efekt domina?

EDYCJA: Kluczowym zwrotem, którego nie użyłem, jest „asymptotyczna klasa aproksymacji” (dzięki Oleksandr). Wydaje się, że w tej dziedzinie jest trochę pracy, ale nie osiągnęła ona jeszcze takiego samego poziomu dojrzałości jak teoria klasycznych klas aproksymacyjnych.

Raphael
źródło
Jaki jest tytuł wspomnianej książki?
Karolina Sołtys,
2
Nie jestem pewien, czy to prawda. Zobacz str. 2 notatek powiązanych z pytaniem, w szczególności twierdzenia 3 i 4 oraz otwarty problem przedstawiony tuż pod twierdzeniem 4. Szczególna książka, o której mówiłem, to Algorytmy aproksymacji autorstwa Vijay Vazirani, co jest doskonałe.
Raphael
Frieze i Kannan ( research.microsoft.com/en-us/um/people/kannan/Papers/... ) podali losowy algorytm stałego czasu z błędem addytywnym epsilon n ^ k dla dowolnego problemu z maksymalnym ograniczeniem satysfakcji z ograniczeniami arity.
Warren Schudy
Myślę, że upakowanie bin w przybliżeniu w ramach OPT + 1 jest całkowicie zgodne z obecną wiedzą. W rzeczywistości konfiguracja LP jest przypuszczana, że ​​ma lukę w integralności addytywnej 1 (uważam tę hipotezę za nieco dziką, ale nie ma znanych kontrprzykładów).
Sasho Nikolov

Odpowiedzi:

23

Pytanie jest dość otwarte, więc nie sądzę, że można na nie całkowicie odpowiedzieć. To jest częściowa odpowiedź.

Łatwa obserwacja polega na tym, że wiele problemów jest nieciekawych, gdy rozważamy addytywne przybliżenie. Na przykład tradycyjnie funkcją celu Max-3SAT jest liczba spełnionych klauzul. W tym sformułowaniu przybliżenie Max-3SAT w ramach błędu addytywnego O (1) jest równoważne dokładnemu rozwiązaniu Max-3SAT, po prostu dlatego, że funkcję celu można skalować, kopiując formułę wejściową wiele razy. Multiplikacyjne przybliżenie jest znacznie bardziej istotne dla tego rodzaju problemów.

[Edycja: We wcześniejszej wersji użyłem Niezależnego zestawu jako przykładu w poprzednim akapicie, ale zmieniłem go na Max-3SAT, ponieważ Niezależny zestaw nie jest dobrym przykładem do zilustrowania różnicy między przybliżeniem mnożącym a przybliżeniem addytywnym; aproksymowanie zestawu niezależnego nawet w obrębie mnożnika O (1) jest również trudne dla NP. W rzeczywistości Håstad [Has99] pokazuje znacznie silniejszą niedopuszczalność niezależnego zestawu.]

Ale, jak powiedziałeś, przybliżenie addytywne jest interesujące w przypadku problemów takich jak pakowanie pojemników, w których nie możemy skalować funkcji celu. Co więcej, często możemy przeformułować problem, aby przybliżenie addytywne stało się interesujące.

Na przykład, jeśli funkcja celu Max-3SAT zostanie ponownie zdefiniowana jako stosunek liczby spełnionych klauzul do całkowitej liczby klauzul (jak to się czasem robi), przybliżenie addytywne staje się interesujące. W tym ustawieniu aproksymacja addytywna nie jest trudniejsza niż aproksymacja multiplikatywna w tym sensie, że aproksymacja w ramach współczynnika multiplikatywnego 1 ε (0 < ε <1) implikuje aproksymację w ramach błędu addytywnego ε , ponieważ optymalna wartość wynosi zawsze maksymalnie 1.

Ciekawym faktem (który wydaje się niestety często pomijany) jest to, że wiele wyników niedopuszczalności dowodzi kompletności NP niektórych problemów z lukąco nie wynika z samej twardości NP multiplikatywnego przybliżenia (patrz także Petrank [Pet94] i Goldreich [Gol05, sekcja 3]). Kontynuując przykład Max-3SAT, jest dobrze znanym wynikiem Håstad [Has01], że NP jest trudne do przybliżenia Max-3SAT przy stałym współczynniku multiplikatywnym lepszym niż 7/8. Sam ten wynik nie wydaje się sugerować, że NP jest trudne do przybliżenia wersji stosunku Max-3SAT przy stałym błędzie addytywnym przekraczającym pewien próg. Jednak to, co udowodnił Håstad [Has01], jest silniejsze niż zwykła multiplikatywna niedopuszczalność: udowadnia, że ​​następujący problem z obietnicą jest NP-zupełny dla każdej stałej 7/8 < s <1:

GAP 3SAT s
wystąpienia : a CNF wzór φ gdzie każdy punkt obejmuje dokładnie trzy różne zmienne.
Tak, obietnica : φ jest satysfakcjonująca.
No-obietnica : Nie prawda spełnia przypisania więcej niż ów ułamek klauzul cp.

Z tego możemy wywnioskować, że NP jest trudny do przybliżenia wersji stosunku Max-3SAT z błędem addytywnym lepszym niż 1/8. Z drugiej strony zwykłe, proste losowe przypisanie daje przybliżenie w ramach błędu addytywnego 1/8. Dlatego wynik Håstad [Has01] nie tylko zapewnia optymalną multiplikatywną niedopuszczalność tego problemu, ale także optymalną niedopuszczalność dodatku. Sądzę, że istnieje wiele takich wyników niedopuszczalności addytywnej, które nie pojawiają się wyraźnie w literaturze.

Referencje

[Gol05] Oded Goldreich. O problemach z obietnicą (ankieta ku pamięci Shimona Evena [1935-2004]). Elektroniczne kolokwium na temat złożoności obliczeniowej , raport TR05-018, luty 2005 r. Http://eccc.hpi-web.de/report/2005/018/

[Has99] Johan Håstad. Klika jest trudna do przybliżenia w granicach n 1− ε . Acta Mathematica , 182 (1): 105–142, marzec 1999 r. Http://www.springerlink.com/content/m68h3576646ll648/

[Has01] Johan Håstad. Niektóre optymalne wyniki niedopuszczalności. Journal of the ACM , 48 (4): 798–859, lipiec 2001. http://doi.acm.org/10.1145/502090.502098

[Pet94] Erez Petrank. Twardość przybliżenia: Lokalizacja szczeliny. Złożoność obliczeniowa , 4 (2): 133-157, kwiecień 1994. http://dx.doi.org/10.1007/BF01202286

Tsuyoshi Ito
źródło
3
Jako kolejny przykład, myślę, że sformułowanie problemu maksymalnego cięcia byłoby dość naturalne, aby zmaksymalizować ułamek krawędzi w cięciu. Ponownie mamy zarówno pozytywne, jak i negatywne wyniki przybliżenia addytywnego.
Jukka Suomela
1
@Jukka, czy możesz podać odniesienie do tego sformułowania Max-cut?
Mohammad Al-Turkistany
1
Dziękuję bardzo. Wydaje się, że jest to obszar wymagający przynajmniej ankiety. O ile wiem, zoo nie wspomina nawet o klasach aproksymacji błędów addytywnych (chociaż jest tak duża, że ​​mogłem coś przeoczyć).
Raphael
@Raphael: Uważam, że ankieta (lub wskaźnik do jednej) jest raczej przydatna. O ile mi wiadomo, klasy algorytmów aproksymacyjnych były ostatnio badane około dziesięć lat temu, a prezentacja była dla mnie niejasna.
András Salamon
6

To jest częściowa odpowiedź

ABSABS

NP

-Każda sześcienna grafika jest wielobarwna na 4 krawędziach w czasie wielomianu, ale kolorowanie krawędzi 3 jest NP-twarde.

ABSP=NP

Mohammad Al-Turkistany
źródło
Dzięki. Zauważam, że ABS nie jest wymieniony w zoo złożoności qwiki.stanford.edu/index.php/Complexity_Zoo:A . Czy masz do tego referencję?
Raphael
Sprawdź to odniesienie, citeseerx.ist.psu.edu/viewdoc/…
Mohammad Al-Turkistany
Czy mam rację, sądząc, że nazwa ABS dla klasy złożoności to nazwa, którą właśnie wymyśliłeś, czy też jest do niej odniesienie? Wydaje się, że zamieszczony link nie wspomina o tym.
Raphael
@ Rafael, Nie, nie zniosłem nazwy ABS, przeczytałem ją gdzieś dawno temu.
Mohammad Al-Turkistany
6

Niedawno pracowano nad asymptotycznymi klasami aproksymacyjnymi i ich porównaniem z klasycznymi odpowiednikami.

Erik Jan van Leeuwen i Jan van Leeuwen. Struktura aproksymacji czasu wielomianowego . Raport techniczny UU-CS-2009-034. Grudzień 2009 r.

Oleksandr Bondarenko
źródło