Algorytmy aproksymacyjne dla metrycznego TSP

Wiadomo, że metryczny TSP może być przybliżony w granicach i nie może być przybliżony lepiej niż $1.5$ w czasie wielomianowym. Czy coś wiadomo na temat znajdowania rozwiązań aproksymacyjnych w czasie wykładniczym (na przykład mniej niż2nkroków z tylko przestrzenią wielomianową)? Np. W jakim czasie i przestrzeni możemy znaleźć trasę, której odległość wynosi co najwyżej1,1×OPT?$123\over 122$$2^n$$1.1\times OPT$

Studiowałem problem i znalazłem najbardziej znane algorytmy dla TSP.

$n$ to liczba wierzchołków,$M$ to maksymalna waga krawędzi. Wszystkie granice są podane do wielomianowego współczynnika wielkości wejściowej ($poly(n, \log M)$ ). Oznaczamy Asymetryczny TSP przez ATSP.

1. Dokładne algorytmy dla TSP

1.1 Ogólne ATSP

$M2^{n-\Omega(\sqrt{n/\log (Mn)})}$czas i$exp$space (Björklund).

$2^n$ czasu i$2^n$ przestrzeni (Bellman;Held, Karp).

$4^n n^{\log n}$ czasu i$poly$ -kosmiczna (Gurewicz, Sela,Björklund, Husfeldt).

$2^{2n-t} n^{\log(n-t)}$ czas i$2^t$ przestrzeni dla$t=n,n/2,n/4,\ldots$ (Koivisto, Parviainen).

$O^*(T^n)$ i przestrzeń$O^*(S^n)$ dla dowolnego$\sqrt2<S<2$z$TS<4$(Koivisto, Parviainen).

$2^n\times M$ iwieloprzestrzeń(Lokshtanov, Nederlof).

$2^n\times M$ czas i przestrzeń$M$ (Kohn, Gottlieb, Kohn;Karp;Bax, Franklin).

$2^n$

1.2 Specjalne przypadki TSP

$1.657^n\times M$

$(2-\epsilon)^n$$\epsilon$

$(2-\epsilon)^n$$poly$$\epsilon$

$1.251^n$$poly$

$1.890^n$$poly$$4$

$1.733^n$$4$

$1.657^n$$poly$

$(2-\epsilon)^n$$d^n$$d$

2. Algorytmy aproksymacyjne dla TSP

2.1 Ogólne TSP

Nie można aproksymować w żadnej funkcji obliczanej w czasie wielomianowym, chyba że P = NP ( Sahni, Gonzalez ).

2.2 Metryczny TSP

$3 \over 2$

$123\over 122$

2.3 Graficzny TSP

$7\over5$

2.4 (1,2) -TSP

MAX-SNP twardy ( Papadimitriou, Yannakakis ).

$8 \over 7$

2.5 TSP w danych z wymiarem ograniczonym

PTAS dla TSP w stałej wymiarowej przestrzeni euklidesowej ( Arora ; Mitchell ).

$\log{n}$

PTAS dla TSP w metrykach z ograniczonym podwajaniem wymiaru ( Bartal, Gottlieb, Krauthgamer ).

2.6 ATSP z ukierunkowaną nierównością trójkąta

$O(1)$

$75\over 74$

2.7 TSP na wykresach z zakazanymi nieletnimi

Czas liniowy PTAS ( Klein ) dla TSP na wykresach planarnych.

PTAS dla niewielkich grafów ( Demaine, Hajiaghayi, Kawarabayashi ).

$22\frac{1}{2}$

$O(\frac{\log g}{\log\log g})$$g$

2.8 MAX-TSP

$7\over9$

$7\over8$

$3\over4$

$35\over44$

2.9 Przybliżenia czasu wykładniczego

$(1+\epsilon)$$2^{(1-\epsilon/2)n}$$\epsilon\le \frac{2}{5}$$4^{(1-\epsilon/2)n} n^{\log n}$$\epsilon \leq \frac{2}{3}$

Byłbym wdzięczny za wszelkie uzupełnienia i sugestie.

$O^*(1.932^n)$$O^*(2^n)$$n$$(1+\epsilon)$$O^*(2^{(1-\epsilon/2)n})$$\epsilon \le 2/5$

Nicolas Boria, Nicolas Bougeois, Bruno Escoffier, Vangelis Th. Paschos: wykładnicze schematy aproksymacji dla niektórych problemów graficznych. Dostępne online .

$\alpha$$\beta$$\alpha < \beta$$\gamma$$\alpha, \beta]$$\gamma$$\theta$$\gamma$$2^{n^{O(\theta)}}$$\gamma$(przynajmniej w zakresie stałych współczynników) zobacz poprawę współczynnika aproksymacji, nawet jeśli podany jest czas wykładniczy. Istnieje kilka problemów, w których najlepszym znanym wynikiem twardości jest nieefektywna redukcja z SAT, to znaczy, że wynik twardości jest przyjęty przez słabsze założenie, takie jak NP nie zawarte w quasi-wielomianowym czasie. W takich przypadkach można uzyskać lepsze przybliżenie w czasie podwykładniczym. Jedyne, o czym wiem, to problem grupowego drzewa Steinera. Ostatnim znanym rezultatem jest Arora-Barak-Steurer z algorytmem czasu podwykładniczego dla unikalnych gier: z tego wyniku wyciągamy wniosek, że jeśli UGC jest prawdą, to redukcja z SAT do UGC musi być nieefektywny, to znaczy rozmiar wystąpienia UGC uzyskanego ze wzoru SAT musi rosnąć wraz z parametrami w określony sposób.

Najlepszą łyżeczką dla ważonych wykresów rodzajów jest http://erikdemaine.org/papers/ContractionTSP_Combinatorica/ .