Zwykle myśli się o zbliżeniu rozwiązań (z gwarancjami) do problemów trudnych dla NP. Czy trwają badania nad zbliżeniem problemów, o których wiadomo, że są w P? To może być dobry pomysł z kilku powodów. Z góry mojej głowy algorytm aproksymacyjny może działać ze znacznie mniejszą złożonością (lub nawet znacznie mniejszą stałą), może zajmować mniej miejsca lub może być znacznie lepiej równoległy.
Również schematy, które zapewniają kompromisy czas / dokładność (FPTAS i PTAS) mogą być bardzo atrakcyjne dla problemów w P z dolnymi granicami, które są niedopuszczalne przy dużych nakładach.
Trzy pytania: czy brakuje mi czegoś, co sprawia, że jest to oczywiście zły pomysł? Czy trwają badania nad opracowaniem teorii tych algorytmów? Jeśli nie, to czy ktoś zna indywidualne przykłady takich algorytmów?
źródło
Odpowiedzi:
Jak podkreśla Jukka, geometria obliczeniowa jest bogatym źródłem problemów, które można rozwiązać w czasie wielomianowym, ale chcemy uzyskać szybkie przybliżenia. Klasycznym „idealnym” wynikiem jest „LTAS” (liniowy schemat aproksymacji czasu), którego czas działania miałby postać - zwykle uzyskuje się je przez wyodrębnienie stałej (poli ( 1 / ϵ )) rozmiar jądra z danych i uruchomienie drogiego algorytmu na tym jądrze, z gwarancją, że dokładne rozwiązanie w jądrze jest przybliżonym rozwiązaniem dla całego wejścia.O ( n + poli ( 1 / ϵ ) ) 1 / ϵ
Istnieje wiele sztuczek, redukcji i zasad, a nowa książka Sariela Har-Peleda jest ich pełna. Nie sądzę, aby istniała jakaś bogata teoria złożoności.
źródło
Niewyczerpująca lista ostatnich prac, które znajdują przybliżone rozwiązania problemów wP.
1) Dużo pracy poświęcono przybliżonym rozwiązaniom dla równań liniowych (symetryczna dominacja po przekątnej) w czasie prawie liniowymO (n⋅polilog(n))
(lista artykułów) http://cs-www.cs.yale.edu/homes/spielman/precon/precon.html
(Ogólnie rzecz biorąc, najbardziej iteracyjne solwery dla równań liniowych mają wspólną zasadę aproksymacji - prawdziwe rozwiązanie. To samo dotyczy iteracyjnych metod rozwiązywania bardziej ogólnych problemów (np. Niektóre programy wypukłe / liniowe)).ϵ
2) Przybliżone rozwiązania dla minimalnych / maksymalnych cięć / przepływów http://people.csail.mit.edu/madry/docs/maxflow.pdfs - t
3) Znalezienie rzadkiego przybliżenia transformaty Fouriera sygnału w czasie podliniowym http://arxiv.org/pdf/1201.2501v1.pdf
4) Znalezienie przybliżonego głównego składnika macierzy http://www.stanford.edu/~montanar/RESEARCH/FILEPAP/GossipPCA.pdf
źródło
Nie jestem świadomy rozwoju ogólnej teorii algorytmów aproksymacyjnych dla problemów w P. Znam jednak pewien problem, który nazywa się wyroczniami przybliżonymi:
Dla nielicznych wykresach bardziej ogólnego czasoprzestrzeni przybliżenie czasu kompromis może być pokazane .
źródło
Często szukamy przybliżonych rozwiązań prostych problemów, takich jak znalezienie najkrótszej ścieżki na wykresie, znalezienie liczby unikalnych elementów w zestawie. Ograniczeniem jest tutaj to, że dane wejściowe są duże i chcemy rozwiązać problem w przybliżeniu za pomocą pojedynczego przejścia danych. Istnieje kilka algorytmów „strumieniowych” zaprojektowanych w celu osiągnięcia przybliżonych rozwiązań w czasie liniowym / prawie liniowym.
źródło
Algorytmy szybkiego aproksymacji dla maksymalnego dopasowania są znane. Najmniejszym, który przychodzi mi do głowy od razu, jest http://arxiv.org/pdf/1112.0790v1.pdf .
źródło
źródło
Myślę, że cały obszar strumieniowania danych i algorytmy sublinearne to wysiłek w tym kierunku. W streamingu danych nacisk kładziony jest na rozwiązywanie problemów w przestrzeni o (n) i idealnie O (polylog (n)), podczas gdy w algorytmach subliniowych próbujesz uzyskać algorytmy o czasie (o). W obu przypadkach często trzeba iść na kompromis, mając losowy algorytm aproksymacji.
Można zacząć od materiału na tej stronie i to .
źródło
źródło
Dimitris wspomina o przybliżeniu transformacji Fouriera. ma to szerokie zastosowanie w kompresji obrazu, np. w algorytmie JPEG. [1] chociaż nie widziałem artykułu, który to podkreśla, wydaje się, że w pewnym sensie kompresję stratną [2] (z pochodnymi limitami) można również traktować jako algorytm aproksymacji czasu P. aspekty aproksymacji są wysoce rozwinięte i dopracowane / wyspecjalizowane w tym sensie, że są zoptymalizowane, tak że nie mogą być postrzegane przez ludzkie widzenie, tj. postrzeganie przez człowieka artefaktów kodowania (z grubsza zdefiniowane jako różnica między aproksymacją a kompresją bezstratną) jest zminimalizowane.
jest to związane z teoriami o tym, jak ludzkie oko postrzega lub samo „przybliża” kodowanie kolorów za pomocą jakiegoś algorytmicznego procesu. innymi słowy, teoretyczny schemat / algorytm aproksymacji jest faktycznie celowo zaprojektowany tak, aby pasował do fizycznego / biologicznego schematu / algorytmu aproksymacji (zakodowany przez przetwarzanie informacji biologicznych, tj. neurony w ludzkim układzie wzrokowym).
więc kompresja jest ściśle powiązana z przybliżeniem. w JPEG transformata Fouriera jest aproksymowana przez DCT, dyskretną transformację kosinusową [3]. podobne zasady stosuje się w przypadku wielu klatek dla standardu kompresji wideo MPEG. [4]
[1] kompresja JPEG, wikipedia
[2] kompresja stratna, wikipedia
[3] DCT, dyskretna transformacja cosinusowa, wikipedia
[4] MPEG, wikipedia
źródło
Być może nie jest to dokładnie odpowiedź na twoje pytanie, ponieważ obecnie pamiętam tylko niektóre heurystyki, ale jestem pewien, że istnieją pewne przybliżenia, ponieważ widziałem je wcześniej.
źródło
http://www.sciencedirect.com/science/article/pii/S0020019002003939
to link do artykułu „Prosty algorytm aproksymacji dla problemu dopasowania ważonego” autorstwa Dorathi Drake i Stefana Hougardy obejmującego problem dopasowania ważonego.
źródło