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

16

Istnieje standardowa teoria aproksymacji, w której stosunek aproksymacji wynosi supAOPT (dla problemów zcelamiMIN),A- wartość zwracana przez niektóre algorytmyAiOPT- wartość optymalna. I inna teoria, żeprzybliżenie różnicowe,gdzie stosunek przybliżenia wynosiinfΩAΩOPT ,Ω- 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 Ω . 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?

Oleksandr Bondarenko
źródło
2
Nigdy wcześniej nie widziałem tego pojęcia i uważam, że jest ono co najmniej interesujące. Bardzo ciekawi odpowiedzi! (chociaż prawdziwy powód może być tak trywialny jak „Doh, nigdy o tym nie myślałem” lub „Dowody stają się coraz trudniejsze” lub „Nie mogę porównać tego z innymi wynikami, kiedy zaczynam”)
Raphael

Odpowiedzi:

3

Istnieją dwa interpretacje zastrz algorytmu „ znajdzie a -approximation problemowego PAα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.CICCja

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?)

Jukka Suomela
źródło
Nie rozumiem o co ci chodzi w drugiej części. Każdy nadmiernie przybliżony wybór wierzchołków jest wykonalną osłoną wierzchołków, nie musimy wiedzieć, że algorytm jest do tego przybliżony. Z drugiej strony, nawet przybliżenie 2 dla niezależnego zestawu może bardzo dobrze dać niewykonalne rozwiązanie. Wydaje się więc, że niebezpieczeństwo niemożności jest związane z problemem, a nie z (nieznanymi) granicami przybliżenia.
Raphael
@Raphael: 2-przybliżenie maksymalnego niezależnego zestawu jest z definicji niezależnym zbiorem (i dość dużym; na pewno nie pustym zbiorem).
Jukka Suomela
Nieważne, czytaj zbyt szybko. Ale nadal uważam, że twój punkt powinien być sformułowany w następujący sposób: Algorytm bez gwarancji przybliżenia wykonuje zadanie w przypadku VC, ale nie w IS. (Porównujesz tam jabłka i gruszki, prawda?) Ale w jaki sposób to badanie odnosi się do wyboru gwarancji? Albo zrobi to, aby wybrać realne rozwiązania.
Raphael
@Raphael: Nie, mówię, że trywialny VC ma skończoną gwarancję przybliżenia (coś takiego jak ) i wykonuje zadanie, podczas gdy trywialny IS nie ma ograniczonej gwarancji przybliżenia i nie otrzymuje praca wykonana. Stąd gwarancje przybliżenia mówią przynajmniej coś o tym, jak przydatne jest to rozwiązanie. O(Δ)
Jukka Suomela
1
+1, ponieważ przykłady są fajne. Nie sądzę, aby istniała dobrze zdefiniowana różnica między „problemem jest łatwym” a „jest dobrym algorytmem”, ale rozumiem go na dość niejasnym poziomie.
Tsuyoshi Ito,
3

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.

Tsuyoshi Ito
źródło
02OPTn/2
@Oleksandr: „W przypadku osłony wierzchołków przybliżenie zbiega się jednak z najgorszym rozwiązaniem, gdy OPT⩾n / 2 mamy stosunek 2.” To, czy uważasz to za wadę, czy nie, jest punktem widzenia. Można argumentować, że jeśli każde rozwiązanie ma wartość celu w granicach 2, to nie ma większego znaczenia, jakie rozwiązanie tworzy algorytm. Standardowy współczynnik przybliżenia modeluje taką sytuację.
Tsuyoshi Ito
Jeśli ten współczynnik 2 lub jakikolwiek inny mały czynnik jest najgorszym rozwiązaniem, taki wynik jest mało przydatny.
Oleksandr Bondarenko
1
@Oleksandr: Tak jak powiedziałem, taki jest punkt widzenia.
Tsuyoshi Ito
3

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.

α=AOPT

α=ΩAΩOPTα100%

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

[Ω,OPT]

Raphael
źródło