Płynna analiza algorytmów aproksymacyjnych

Wygładzona analiza była stosowana wiele razy, aby zrozumieć czas działania dokładnych algorytmów dla wielu problemów, takich jak programowanie liniowe i k-średnich. Istnieją dość ogólne wyniki w tej dziedzinie, na przykład Heiko Röglin i Berthold Vöcking, Analiza wygładzania programowania liczb całkowitych , 2005. Niektóre z tych ogólnych wyników wydają się polegać na lematach izolacji w celu stworzenia instancji z unikalnym optymalnym rozwiązaniem. Zakładając, że , niniejszy artykuł wyklucza istnienie wygładzonych wielomianowych algorytmów czasowych dla problemów z twardością N $\mathsf{NP}\ne \mathsf{ZPP}$$\mathsf{NP}$

Wykonano pewne prace nad wygładzoną analizą współczynników algorytmu aproksymacyjnego. Istnieje Rao Raghavendra, Probabilistyczna i wygładzona analiza algorytmów aproksymacyjnych , 2008, która próbuje uzyskać lepsze przybliżenie związane z algorytmem Christofidesa z wygładzoną analizą. Nie podano jednak wyraźnego współczynnika przybliżenia.

Czy jest jakiś powód, dla którego twardość wyników aproksymacji powinna ograniczać współczynniki aproksymacji algorytmów działających w wygładzonym czasie wielomianowym? Czy wyniki w pracy Heiko Röglin i Bertholda Vöckinga dotyczą również algorytmów aproksymacyjnych?

Artykuł Bläser, Panagiotou i Rao dotyczy koncentracji trasy wyprodukowanej przez algorytm Christofidesa. Nie zastrzega się współczynnika przybliżenia średniego przypadku, z wyjątkiem niektórych wyników eksperymentalnych.

Artykuł Röglina i Vöckinga (Math. Program., 2007) oraz wcześniejszy artykuł Beiera i Vöckinga (SIAM J. Comput., 2006) z grubsza stwierdzają, że wygładzony czas wielomianowy jest równoważny losowemu pseudopolimialnemu czasowi. Pseudo-wielomian oznacza tutaj wielomian czasu wykonywania w wielkości wejściowej i wielkości zaburzonych współczynników. Wyklucza to wygładzoną złożoność wielomianową w przypadku problemów z optymalizacją NP-twardą (chyba że NP = ZPP).

Jeśli chodzi o płynną analizę i aproksymację, jest bardzo niewiele prac, które dotyczą konkretnych problemów lub algorytmów (Englert, Röglin i Vöcking dla heurystyki 2-opt dla TSP; Bläser, Manthey i Rao, a także Curticapean i Künnemann dla podziału heurystyk; Karger i Onak do pakowania wielowymiarowego). Nie znam jednak żadnych powiązań strukturalnych między niedopuszczalnością a wygładzoną analizą.