Wiadomo, że metryczny TSP może być przybliżony w granicach i nie może być przybliżony lepiej niż 123 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?
cc.complexity-theory
graph-algorithms
approximation-algorithms
tsp
exp-time-algorithms
Alex Golovnev
źródło
źródło
Odpowiedzi:
Studiowałem problem i znalazłem najbardziej znane algorytmy dla TSP.
1. Dokładne algorytmy dla TSP
1.1 Ogólne ATSP
1.2 Specjalne przypadki TSP
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
2.3 Graficzny TSP
2.4 (1,2) -TSP
MAX-SNP twardy ( Papadimitriou, Yannakakis ).
2.5 TSP w danych z wymiarem ograniczonym
PTAS dla TSP w stałej wymiarowej przestrzeni euklidesowej ( Arora ; Mitchell ).
PTAS dla TSP w metrykach z ograniczonym podwajaniem wymiaru ( Bartal, Gottlieb, Krauthgamer ).
2.6 ATSP z ukierunkowaną nierównością trójkąta
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 ).
2.8 MAX-TSP
2.9 Przybliżenia czasu wykładniczego
Byłbym wdzięczny za wszelkie uzupełnienia i sugestie.
źródło
Nicolas Boria, Nicolas Bougeois, Bruno Escoffier, Vangelis Th. Paschos: wykładnicze schematy aproksymacji dla niektórych problemów graficznych. Dostępne online .
źródło
źródło
Najlepszą łyżeczką dla ważonych wykresów rodzajów jest http://erikdemaine.org/papers/ContractionTSP_Combinatorica/ .
źródło