Algorithmes d'approximation pour métrique TSP

44

Il est connu que la PST métrique peut être approximée dans un et ne peut pas être mieux estimée que 1231.5 en temps polynomial. Est-il connu quoi que ce soit sur la recherche de solutions d'approximation en temps exponentiel (par exemple, moins de2npas avec seulement un espace polynomial)? Par exemple, dans quel temps et dans quel espace pouvons-nous trouver un circuit dont la distance est au pluségaleà1,1×OPT?1231222n1.1×OPT

Alex Golovnev
la source
3
Une approche naturelle pour répondre aux questions de ce type est de regarder les hiérarchies de programmation linéaires tels que Sherali-Adams, Lovász-Schrijver, ou Lasserre, qui permet de faire tourner le temps au r e niveau (et le plus souvent de plus en plus meilleures approximations à mesure que r grandit). Cependant, je ne suis au courant d'aucun résultat, positif ou négatif, concernant l'applicabilité des hiérarchies sur l'assouplissement LP de TSP métriques (connu sous le nom de Held-Karp). poly(nr)rr
HME
3
Vous voulez probablement dire "possible" plutôt que "nécessaire"? De plus, je ne suis pas sûr de ce que vous entendez par trouver des solutions en temps exponentiel, car je peux toujours trouver la réponse exacte. Je suppose que vous voulez dire "trouver de meilleurs points sur la courbe d’ajustement approximation / complexité"?
Suresh Venkat
@MCH, merci beaucoup, mais je n'ai trouvé aucun résultat.
Alex Golovnev
@Suresh Venkat, merci! Vous avez absolument raison, je veux dire "possible" et "meilleur point ...". J'ai corrigé ma question.
Alex Golovnev
En ce qui concerne le TSP métrique avec le point de départ et le point d'arrivée spécifiés, le meilleur est la connaissance est . Un article de STOC 2012 intitulé "Amélioration de l'algorithme de Christofides pour le TSP" st Path "à l'adresse arxiv.org/abs/1110.4604. 1+52
Peng Zhang

Réponses:

53

J'ai étudié le problème et j'ai trouvé les algorithmes les plus connus pour TSP.

n est le nombre de sommets,M est le poids maximal de l'arête. Toutes les bornes sont attribuées à un facteur polynomial de la taille de l'entrée (poly(n,logM) ). Nous désignons TSP asymétrique par ATSP.

1. Algorithmes Exacts pour TSP

1.1. ATSP général

M2nΩ(n/log(Mn))heure etexp-space (Björklund).

2n temps et2n espace (Bellman;Held, Karp).

4nnlogn fois etpoly -space (Gurevich, Chéla;Björklund, Husfeldt).

22ntnlog(nt) temps et2t espace pourt=n,n/2,n/4, (Koivisto, Parviainen).

O(Tn) temps etO(Sn) espace pour tout2<S<2avecTS<4(Koivisto, Parviainen).

2n×M temps et espacemultiple(Lokshtanov, Nederlof).

2n×M temps et espaceM (Kohn, Gottlieb, Kohn;Karp;Bax, Franklin).

2n

1.2. Cas spéciaux de TSP

1.657n×M

(2ϵ)nϵ

(2ϵ)npolyϵ

1.251npoly

1.890npoly4

1.733n4

1.657npoly

(2ϵ)ndnd

2. Algorithmes d'approximation pour TSP

2.1. TSP général

Ne peut être approché dans aucune fonction calculable en temps polynomial sauf si P = NP ( Sahni, Gonzalez ).

2.2. TSP métrique

32

123122

2.3. TSP graphique

75

2.4. (1,2) -TSP

MAX-SNP dur ( Papadimitriou, Yannakakis ).

87

2.5. TSP dans les métriques avec dimension bornée

PTAS pour TSP dans un espace euclidien de dimension fixe ( Arora ; Mitchell ).

logn

PTAS pour TSP en métriques avec dimension de doublage limitée ( Bartal, Gottlieb, Krauthgamer ).

2.6 ATSP avec inégalité de triangle dirigée

O(1)

7574

2.7 TSP dans les graphiques avec les mineurs interdits

PTAS à temps linéaire ( Klein ) pour TSP dans les graphes planaires.

PTAS pour les graphes sans mineur ( Demaine, Hajiaghayi, Kawarabayashi ).

2212

O(loggloglogg)g

2.8. MAX-TSP

79

78

34

3544

2.9 Approximations de temps exponentiel

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

Je serais reconnaissant pour tout ajout et suggestion.

Alex Golovnev
la source
5
Ceci est un excellent résumé de ce que l'on sait. Je vous encourage à accepter cette réponse (même si c'est la vôtre).
Suresh Venkat
1
Nullpick mineur: il semble que vous ayez changé de place pour les constantes d'inapproximabilité pour TSP métrique et ATSP.
Michael Lampis
2
Vous pouvez ajouter des graphes mineurs planaires / genres bornés / exclus; les résultats dont je suis au courant sont les suivants. (1) TSP dans les graphes planaires - PTAS à temps linéaire ( cs.brown.edu/people/klein/publications/no-contraction.pdf ), (2) TSP dans les graphes mineurs limités / exclus - QPTAS pour les graphes non pondérés avec des mineurs exclus / graphes pondérés avec genre lié ( cs.emory.edu/~mic/papers/15.pdf ), (3) ATSP dans les graphes planaires - approximation constante du facteur ( stanford.edu/~saberi/atsp2.pdf ).
Zotachidil
4
@ Alex Golovnev: L'algorithme de Björklunds ne fonctionne pas pour ATSP, il dépend de manière cruciale de la symétrie du graphe.
Andreas Björklund
3
Le résultat de Erickson-Sidiropoulos est pour ATSP - ce n'est pas clair dans la liste ci-dessus. Le PTAS d’Arora fonctionne pour toute dimension fixe. Je n'aime pas le terme "ATSP métrique".
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: schémas d'approximation exponentielle pour certains problèmes de graphes. Disponible en ligne .

Vincenzo
la source
10

αβα<βγα,β]γθγ2nO(θ)γ(du moins dans la gamme des facteurs constants) constatent des améliorations du rapport d’approximation même lorsque le temps sous-exponentiel est donné. Il existe plusieurs problèmes pour lesquels le meilleur résultat de dureté connu consiste en une réduction inefficace du SAT, c'est-à-dire que le résultat de la dureté est sous une hypothèse plus faible, telle que NP non contenu dans un temps quasi-polynomial. Dans de tels cas, on peut obtenir une meilleure approximation en temps sub-exponentiel. Le seul que je connaisse est le problème du groupe Steiner. Un résultat récent et célèbre est celui d'Arora-Barak-Steurer sur un algorithme sous-exponentiel-temporel pour des jeux uniques. inefficace, c’est-à-dire que la taille de l’instance de UGC obtenue à partir de la formule SAT doit croître avec les paramètres d’une certaine manière.

Chandra Chekuri
la source
2n