Teoretyczne zastosowania algorytmów aproksymacyjnych

21

Ostatnio zacząłem szukać algorytmów aproksymacyjnych dla problemów trudnych dla NP i zastanawiałem się nad teoretycznymi przyczynami ich badania. (To pytanie nie ma być zapalne - jestem po prostu ciekawy).

Z badań algorytmów aproksymacyjnych wynikła pewna naprawdę piękna teoria - związek między twierdzeniem PCP a twardością aproksymacji, hipoteza UGC, algorytm aproksymacji Goemana-Williamsona itp.

Zastanawiałem się jednak nad punktem studiowania algorytmów aproksymacyjnych dla problemów takich jak Traveling Salesman, Asymmetric Traveling Salesman i inne warianty, różne problemy w projektowaniu mechanizmów (na przykład w aukcjach kombinatorycznych) itp. Czy takie algorytmy aproksymacyjne były przydatne w innych częściach teorii w przeszłości, czy są one studiowane wyłącznie dla nich samych?

Uwaga: Nie pytam o żadne praktyczne zastosowania, ponieważ o ile wiem, w prawdziwym świecie stosuje się głównie heurystykę, a nie algorytmy aproksymacyjne, a heurystyka rzadko jest informowana przez jakiekolwiek spostrzeżenia uzyskane dzięki badaniu algorytmów aproksymacyjnych dla problem.

Anon1234
źródło
4
Nie jestem pewien, czy rozumiem pytanie. Jakie są „teoretyczne powody” studiowania jakiegokolwiek przedmiotu teoretycznego?
Jeffε
1
Myślę, że ma na myśli „wypełnij itp.” w ust. 2
Huck Bennett,
2
Czy to źle, jeśli to właśnie robię i nigdy nie zadałem sobie pytania? Pomyślałem, że algorytmy aproksymacyjne wyglądają świetnie!
Gopi,
1
Myślę, że motywacja jest taka sama jak motywacja do badania twardości aproksymacji: do zrozumienia dokładnej złożoności różnych problemów. Algorytm Goemansa-Williamsona idzie w parze z wyjątkową twardością gier, która jest lepsza niż współczynnik przybliżenia GW.
Aaron Roth,
1
Nie jestem pewien, czy twój ostatni akapit jest sprawiedliwy. Algorytmy aproksymacji są interesujące, ponieważ są one zaproponował sposób radzenia sobie z problemami takimi jak krnąbrność TSP. Może się zdarzyć, że wiele z nich nie jest bezpośrednio wykorzystywanych w praktyce w oryginalnej formie, ale pomagają wiedzieć, co należy wypróbować. Możesz powiedzieć to samo o dokładnych algorytmach, wiele z nich nigdy nie jest wykorzystywanych bezpośrednio w praktyce, istnieje wiele problemów inżynieryjnych, które należy wziąć pod uwagę, stosując dowolny algorytm w praktyce. Wiele problemów w praktyce nie wymaga dokładnych algorytmów, a użytkownicy będą całkowicie zadowoleni
Kaveh

Odpowiedzi:

21

Zdecydowanie nie zgadzam się z ostatnim akapitem. Takie instrukcje zbiorcze nie są przydatne. Jeśli spojrzysz na dokumenty z wielu dziedzin systemów, takich jak sieci, bazy danych, sztuczna inteligencja itp., Zobaczysz, że w praktyce stosuje się wiele algorytmów aproksymacyjnych. Istnieje kilka problemów, na które można uzyskać bardzo dokładne odpowiedzi; powiedzmy na przykład, że linia lotnicza interesuje się optymalizacją harmonogramu floty. W takich przypadkach ludzie używają różnych heurystyk, które zajmują dużo czasu obliczeniowego, ale uzyskują lepsze wyniki niż może dać ogólny algorytm aproksymacyjny.

Teraz z kilku teoretycznych powodów studiowania algorytmów aproksymacyjnych. Po pierwsze, co tłumaczy fakt, że plecak jest bardzo łatwy w praktyce, a kolorowanie grafów dość trudne? Oba są NP-twarde i redukują się względem siebie w czasie wielokrotnym. Po drugie, badając algorytmy aproksymacyjne dla specjalnych przypadków problemu, można dokładnie określić, które klasy instancji mogą być łatwe lub trudne. Na przykład wiemy, że wiele problemów dopuszcza PTAS w grafach płaskich i bezobsługowych, podczas gdy są one znacznie trudniejsze w dowolnych grafach ogólnych. Idea aproksymacji przenika nowoczesny projekt algorytmu. Na przykład ludzie używają algorytmów przesyłania danych i bez obiektywu aproksymacyjnego trudno jest zrozumieć / zaprojektować algorytmy, ponieważ nawet prostych problemów nie da się dokładnie rozwiązać.

Chandra Chekuri
źródło
12

S.2)pZP.P.N.P.

Markus Bläser
źródło
9

Nie zgadzam się również z „notatką”, przynajmniej wyrażoną w tej ogólności. W związku z tym, czy ktoś wie, czy wygrana Davida Johnsona w Kanellakis jest dostępna gdzieś?

Ponadto, gdy uświadomimy sobie, że wszystkie problemy trudne dla NP są równoważne w odniesieniu do najgorszego przypadku złożoności dokładnych rozwiązań, bardzo naturalne jest zapytanie o złożoność znalezienia przybliżonych rozwiązań. A Chandra świetnie podkreśla zmianę perspektywy, jaką algorytmy aproksymacyjne wnoszą do projektowania algorytmów.

O(logn)

Sasho Nikolov
źródło
8

Najlepszą heurystyką są algorytmy aproksymacyjne. Najpiękniejsze algorytmy aproksymacyjne to po prostu „głupie” heurystyki, które działają. Na przykład lokalne wyszukiwanie klastrów, zachłanne grupowanie (Gonzalez), jedno w cenie dwóch, różne algorytmy zachłanne itp. Itd.

Zatem badanie algorytmów aproksymacyjnych polega na zrozumieniu, jakie heurystyki są gwarantowanymi algorytmami aproksymacyjnymi. Mamy nadzieję, że badania nad algorytmami aproksymacyjnymi tworzą dwa rodzaje zapłodnienia krzyżowego:

  • Przenieś pomysły działające z heurystyki na narzędzia do projektowania algorytmów. Podobnie przenieś pomysły z projektowania algorytmów na heurystykę / algorytmy, które sprawdzają się w praktyce.
  • krzyżowe zapłodnienie między osobą, która właśnie ukończyła szkołę, a stanowiskiem.

Krótko mówiąc, świat nie jest dokładny, dane wejściowe nie są dokładne, funkcje celu zoptymalizowane przez różne problemy algorytmiczne nie są dokładne i co najwyżej stanowią rozmyte przybliżenie tego, czego się chce, a obliczenia nie są dokładne. Dlaczego ktokolwiek miałby uczyć się dokładnych algorytmów? (Odpowiedź: Ponieważ dokładne algorytmy są naprawdę dobrymi algorytmami aproksymacyjnymi).

W prawdziwym świecie jest bardzo mało dokładnych algorytmów - musisz użyć przybliżenia, aby być zdalnie istotne ...

Sariel Har-Peled
źródło
4

Radzenie sobie z problemami z ciągłymi zmiennymi jest bardzo denerwujące przy dokładnych algorytmach. Na przykład, co oznacza określenie wag krawędzi wystąpienia TSP z dokładnymi liczbami rzeczywistymi?

Gdy zezwolimy na algorytmy FPTAS dla tych problemów, możemy kwantyzować te parametry do liczb całkowitych. Sprawia to, że problem jest znacznie lepiej zachowywany (można używać standardowych maszyn Turinga), ale powoduje niewielki błąd.

David Harris
źródło