Algorytmy aproksymacyjne dla problemów w P.

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?

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 + \text{poly}(1/\epsilon))$$1/\epsilon$

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.

Niewyczerpująca lista ostatnich prac, które znajdują przybliżone rozwiązania problemów w $P$

1) Dużo pracy poświęcono przybliżonym rozwiązaniom dla równań liniowych (symetryczna dominacja po przekątnej) w czasie prawie liniowym $\mathcal{O}(n\cdot\text{polylog}(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)).$\epsilon$

2) Przybliżone rozwiązania dla minimalnych / maksymalnych cięć / przepływów http://people.csail.mit.edu/madry/docs/maxflow.pdf$s-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

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:

Biorąc pod uwagę ważony niekierowany wykres z n = | V | węzły i m = | E | Krawędzie, zapytanie punkt-punkt prosi o odległości między dwoma węzłami s , t ∈ V .$G = (V, E)$$n = |V|$$m = |E|$$s, t \in V$

$1$$O(1)$$O(m + n\log n)$

$k$

Dla nielicznych wykresach bardziej ogólnego czasoprzestrzeni przybliżenie czasu kompromis może być pokazane .

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.

$O(nm)$$n$$m$

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 .

$P$

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 .

$\epsilon$$\epsilon$. Istnieje wiele artykułów na temat rozwiązywania specjalnych przypadków problemów programowania liniowego, takich jak przepływy wielokomorowe (a bardziej ogólnie pakowanie i pokrywanie płyt LP). Nie ma osobnej teorii przybliżenia problemów w P w porównaniu z problemami w NP (nie wiemy, czy P jest równe NP czy nie). Można mówić o pewnej technice stosowanej do określonej klasy problemów. Na przykład znane są ogólne techniki przybliżonego rozwiązywania pakowania i obejmowania programów liniowych i niektórych wariantów.

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

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.

$O(f(k)*|G|^\alpha)$$f(k)$ problem i jego późniejsze aproksymacje / heurystyka (proste google pokazuje wyniki w 2010, 2011 r.) lub algorytmy wyszukiwania drzewnego rozkładu grafów.

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.