Twardość aproksymacji - błąd addytywny

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.

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

To jest częściowa odpowiedź

$ABS$$ABS$

$NP$

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

$ABS$$P=NP$

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.