Teoretyczne zastosowania algorytmów aproksymacyjnych

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.

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ć.

$S_2^p \subseteq ZPP^{NP}$

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(\log n)$

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 ...

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.