Dlaczego różnicowe współczynniki aproksymacji nie są dobrze zbadane w porównaniu ze standardowymi pomimo deklarowanych korzyści?

Istnieje standardowa teoria aproksymacji, w której stosunek aproksymacji wynosi $\sup\frac{A}{OPT}$ (dla problemów zcelami$MIN$),$A$- wartość zwracana przez niektóre algorytmy$A$i$OPT$- wartość optymalna. I inna teoria, żeprzybliżenie różnicowe,gdzie stosunek przybliżenia wynosi$\inf\frac{\Omega-A}{\Omega-OPT}$ ,$\Omega$- najgorsza wartość wykonalnego rozwiązania dla danego wystąpienia. Doautorówz tego twierdzenia teorii, że ma jakieś konkretne korzyści w stosunku do klasycznego jednego. Na przykład:

• daje taki sam współczynnik aproksymacji dla takich problemów, jak Minimalna osłona wierzchołków i Maksymalny niezależny zestaw, o których wiadomo, że są tylko różnymi realizacjami tego samego problemu;
• daje ten sam stosunek dla wersji maksymalnej i minimalnej tego samego problemu. Jednocześnie wiemy, że w standardowej teorii MIN TSP i MAX TSP mają bardzo różne stosunki.
• Mierzy odległość nie tylko optymalną, ale także pessimum $\Omega$ . Tak więc w przypadku Vertex Cover standardowa teoria aproksymacji mówi, że $2$ jest najlepszą górną granicą. Ale niezbędna $2$ to maksymalny stosunek między pessimum i optimum. W ten sposób gwarantuje się, że taki algorytm wygeneruje rozwiązanie o najgorszej wartości.

Mój argument pro brzmi: w analizie asymptotycznej nie bierzemy pod uwagę stałych i terminów niskiego rzędu (tutaj przypomniałem cytat Avi Widgersona: „Odnosimy sukces, ponieważ używamy odpowiedniego poziomu abstrakcji”) i to jest poziom abstrakcji do porównywania wykorzystania zasobów przez algorytm. Ale kiedy studiujemy przybliżenie, z jakiegoś powodu wprowadzamy różnicę w tych miejscach, w których możemy jej uniknąć.

Moje pytanie brzmi

dlaczego teoria przybliżania różnicowego jest tak słabo zbadana. Czy związane z tym argumenty nie są wystarczająco silne?

Istnieją dwa interpretacje zastrz algorytmu „ znajdzie a -approximation problemowego P ”$A$$\alpha$$P$ :

1. Problem jest łatwy do rozwiązania dość dobrze, ponieważ mamy algorytm, który znajduje dobre przybliżenie.$P$
2. Algorytm jest dobry , ponieważ znajduje dobre przybliżenie.$A$

Myślę, że klasyczna definicja współczynnika aproksymacji podkreśla pierwszą interpretację. Klasyfikujemy problemy według tego, jak łatwo można je dość dobrze rozwiązać.

Różnicowy współczynnik aproksymacji wydaje się kłaść nieco większy nacisk na drugą interpretację: nie chcemy „nagradzać” trywialnych algorytmów (np. Algorytmów, które po prostu generują pusty zbiór lub zbiór wszystkich węzłów).

Oczywiście oba są poprawnymi punktami widzenia, ale są różnymi punktami widzenia.

Możemy również przestudiować to pytanie z nieco bardziej praktycznej perspektywy. Niestety okładki wierzchołków jako takie nie mają tak wielu bezpośrednich zastosowań, ale dla celów argumentacji rozważmy te dwie (nieco wymyślone) aplikacje:

• Pokrywa wierzchołków: węzły to komputery, a krawędzie to łącza komunikacyjne; chcemy monitorować wszystkie łącza komunikacyjne, a zatem co najmniej jeden punkt końcowy każdej krawędzi musi uruchomić specjalny proces.

• Niezależny zestaw: węzły są pracownikami i modelują konflikty między ich działaniami; chcemy znaleźć zestaw konfliktów działań, które można wykonywać jednocześnie.

Teraz oba problemy mają trywialne rozwiązanie: zestaw wszystkich węzłów jest pokrywą wierzchołków, a pusty zbiór jest zbiorem niezależnym.

Najważniejsza różnica polega na tym, że w przypadku problemu z pokrywą wierzchołków trywialne rozwiązanie wykonuje zadanie . Oczywiście zużywamy więcej zasobów niż to konieczne, ale przynajmniej mamy rozwiązanie, które możemy wykorzystać w praktyce. Jednak w przypadku problemu z niezależnym zestawem trywialne rozwiązanie jest całkowicie bezużyteczne . W ogóle nie robimy postępów. Nikt nic nie robi. Zadanie nigdy nie jest zakończone.

Podobnie, możemy porównać niemal trywialne rozwiązania: problem pokrycia wierzchołkowego , który składa się z punktami końcowymi dopasowaną maksymalnej i niezależnego zestawu I , który jest dopełnieniem C . Ponownie C z pewnością wykonuje zadanie w naszej aplikacji i tym razem nie marnujemy zasobów więcej niż dwa razy. Jednak ja może być ponownie zbiorem pustym, który jest całkowicie bezużyteczny.$C$$I$$C$$C$$I$

Dlatego standardowa definicja gwarancji zbliżenia mówi nam bezpośrednio, czy rozwiązanie jest przydatne, czy nie. 2-przybliżenie osłony wierzchołków wykonuje zadanie. Niezależny zestaw bez gwarancji przybliżenia może być całkowicie bezużyteczny.

W pewnym sensie różnicowy współczynnik przybliżenia próbuje zmierzyć „jak nietrywialne” jest rozwiązanie, ale czy ma to znaczenie w którejkolwiek z tych aplikacji? (Czy to ma znaczenie w jakiejkolwiek aplikacji?)

Pojęcie przybliżenia różnicowego nie jest mi znane i nie mam teorii, dlaczego nie jest on dobrze zbadany. Chciałbym jednak zauważyć, że nie zawsze jest pożądane opisywanie wydajności algorytmu aproksymacji za pomocą pojedynczej miary. W tym sensie trudno mi się zgodzić, że jeden środek jest lepszy niż inny.

Na przykład, jak już wspomniano, minimalna osłona wierzchołków dopuszcza algorytm 2-czasowej aproksymacji w czasie wielomianowym, natomiast NP jest trudne do przybliżenia maksymalnego niezależnego zestawu dla dowolnego stałego stosunku. Chociaż rozumiem, że może to być zaskakujące na pierwszy rzut oka, ma uzasadnione znaczenie: (1) minimalna osłona wierzchołków może być dobrze przybliżona, gdy jest mała, ale (2) nie może być dobrze przybliżona, gdy jest duża. Kiedy stwierdzamy, że NP jest trudne do przybliżenia minimalnego pokrycia wierzchołków (i maksymalnego zestawu niezależnego) przy jakimkolwiek dodatnim stałym stałym przybliżeniu różnicowym, skutecznie ignorujemy właściwość (1). Prawdopodobnie wystarcza do niektórych celów zignorowanie właściwości (1), ale z pewnością nie zawsze tak jest.

Należy pamiętać, że nie zawsze używamy współczynnika aproksymacji do opisania wydajności algorytmów aproksymacyjnych. Na przykład, aby podać wynik niedopuszczalności oparty na twierdzeniu PCP w jego pełnej ogólności, potrzebujemy sformułowania opartego na problemach przerwy. Szczegóły znajdują się w mojej odpowiedzi na inne pytanie . W tym przypadku ani użycie standardowego współczynnika aproksymacji, ani użycie różnicowego współczynnika aproksymacji nie pozwala nam określić wyniku w pełnej ogólności.

Jak zauważa Tsuyoshi, problemem może być to, jakiego rodzaju argumentu chcesz użyć uzyskanego ograniczenia. Poniżej postaram się rozwinąć dwie różne motywacje.

$\alpha = \frac{A}{OPT}$

$\alpha = \frac{\Omega - A}{\Omega - OPT}$$\alpha\cdot 100\%$

Tak więc, w zależności od tego, jakiego rodzaju oświadczenie ma być pochodną, ​​powinieneś wybrać właściwą alternatywę.

$[\Omega, OPT]$