Algorytmy aproksymacyjne dla metrycznego TSP

44

Wiadomo, że metryczny TSP może być przybliżony w granicach i nie może być przybliżony lepiej niż 1231.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?1231222n1.1×OPT

Alex Golovnev
źródło
3
Naturalny podejście do rozwiązania problemów tego typu jest patrzeć liniowych hierarchii programowania, takich jak Sherali Adams, Lovász-Schrijver lub Lasserre, które pozwalają na czas trwania na R p na poziomie (i zwykle bardziej lepsze przybliżenia w miarę wzrostu r ). Nie znam jednak żadnych pozytywnych ani negatywnych wyników dotyczących zastosowania hierarchii w relaksacji LP metryki TSP (znanej jako Held-Karp). poly(nr)rr
MCH
3
Prawdopodobnie masz na myśli raczej „możliwe” niż „potrzebne”? Nie jestem też pewien, co masz na myśli, szukając rozwiązań w czasie wykładniczym, ponieważ zawsze mogę znaleźć dokładną odpowiedź. Zakładam, że masz na myśli „znaleźć lepsze punkty na krzywej kompromisu przybliżenia / złożoności”?
Suresh Venkat,
@MCH, dziękuję bardzo, ale nie znalazłem żadnych wyników.
Alex Golovnev,
@Suresh Venkat, dziękuję! Masz absolutną rację, mam na myśli „możliwy” i „lepszy punkt ...”. Naprawiłem swoje pytanie.
Alex Golovnev,
Jeśli chodzi o metryczny TSP z określonym punktem początkowym i końcowym, najlepszą wartością jest . Artykuł STOC 2012 „Poprawa algorytmu Christofides dla st Path TSP” na stroniearxiv.org/abs/1110.4604. 1+52
Peng Zhang

Odpowiedzi:

53

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,logM) ). Oznaczamy Asymetryczny TSP przez ATSP.

1. Dokładne algorytmy dla TSP

1.1 Ogólne ATSP

M2nΩ(n/log(Mn))czas iexpspace (Björklund).

2n czasu i2n przestrzeni (Bellman;Held, Karp).

4nnlogn czasu ipoly -kosmiczna (Gurewicz, Sela,Björklund, Husfeldt).

22ntnlog(nt) czas i2t przestrzeni dlat=n,n/2,n/4, (Koivisto, Parviainen).

O(Tn) i przestrzeńO(Sn) dla dowolnego2<S<2zTS<4(Koivisto, Parviainen).

2n×M iwieloprzestrzeń(Lokshtanov, Nederlof).

2n×M czas i przestrzeńM (Kohn, Gottlieb, Kohn;Karp;Bax, Franklin).

2n

1.2 Specjalne przypadki TSP

1.657n×M

(2ϵ)nϵ

(2ϵ)npolyϵ

1.251npoly

1.890npoly4

1.733n4

1.657npoly

(2ϵ)ndnd

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

32

123122

2.3 Graficzny TSP

75

2.4 (1,2) -TSP

MAX-SNP twardy ( Papadimitriou, Yannakakis ).

87

2.5 TSP w danych z wymiarem ograniczonym

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

logn

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)

7574

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 ).

2212

O(loggloglogg)g

2.8 MAX-TSP

79

78

34

3544

2.9 Przybliżenia czasu wykładniczego

(1+ϵ)2(1ϵ/2)nϵ254(1ϵ/2)nnlognϵ23

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

Alex Golovnev
źródło
5
To świetne podsumowanie tego, co wiadomo. Zachęcam do zaakceptowania tej odpowiedzi (nawet jeśli jest to Twoja własna).
Suresh Venkat
1
Drobny nitpick: wydaje się, że zamieniłeś miejsca dla stałych niedopuszczalności dla Metric TSP i ATSP.
Michael Lampis,
2
Możesz dodać planarny / związany rodzaj / wykluczone drobne wykresy; wyniki, o których wiem, są następujące. (1) TSP na wykresach planarnych - PTAS w czasie liniowym ( cs.brown.edu/people/klein/publications/no-contraction.pdf ), (2) TSP w ograniczonym rodzaju / wykluczonych mniejszych wykresach - QPTAS dla nieważonych wykresów z wykluczonymi małoletnimi / ważone wykresy z ograniczonym rodzajem ( cs.emory.edu/~mic/papers/15.pdf ), (3) ATSP na wykresach płaskich - przybliżenie współczynnika stałego ( stanford.edu/~saberi/atsp2.pdf ).
zotachidil
4
@Alex Golovnev: Algorytm Björklundsa nie działa dla ATSP, zależy przede wszystkim od symetryczności wykresu.
Andreas Björklund,
3
Wynik Erickson-Sidiropoulos dotyczy ATSP - nie jest jasne na powyższej liście. PTAS Arora działa dla każdego stałego wymiaru. Nie podoba mi się termin „metryczny ATSP”.
Chandra Chekuri,
27

O(1.932n)O(2n)n(1+ϵ)O(2(1ϵ/2)n)ϵ2/5

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

Vincenzo
źródło
10

αβα<βγα,β]γθγ2nO(θ)γ(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.

Chandra Chekuri
źródło
2n
1

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

Gość
źródło
dziękuję, ale czy nie jest to szczególny przypadek wyniku Demaine-Hajiaghayi-Kawarabayashi wskazanego przez Christiana Sommera?
Alex Golovnev