Algoritmos de aproximação para TSP métrico

44

Sabe-se que o TSP métrico pode ser aproximado dentro de e não pode ser aproximado melhor que 1231.5 em tempo polinomial. Existe algo conhecido sobre como encontrar soluções de aproximação em tempo exponencial (por exemplo, menos de2netapas com apenas espaço polinomial)? Por exemplo, em que tempo e espaço podemos encontrar um passeio cuja distância seja no máximo1,1×OPT?1231222n1.1×OPT

Alex Golovnev
fonte
3
Uma abordagem natural para abordar questões deste tipo é olhar para hierarquias de programação linear como Sherali-Adams, Lovász-Schrijver, ou Lasserre, que permitem que executam o tempo no r th nível (e, geralmente, cada vez mais melhores aproximações à medida que r cresce). No entanto, não estou ciente de nenhum resultado positivo ou negativo sobre a aplicabilidade de hierarquias no relaxamento de LP do TSP métrico (conhecido como Held-Karp). poly(nr)rr
MCH
3
Você provavelmente quer dizer "possível" ao invés de "necessário"? Além disso, não sei o que você quer dizer com encontrar soluções em tempo exponencial, pois sempre posso encontrar a resposta exata. Eu suponho que você quer dizer "encontrar melhores pontos na curva de troca de aproximação / complexidade"?
Suresh Venkat
@MCH, muito obrigado, mas não encontrei nenhum resultado.
Alex Golovnev 8/12
@Suresh Venkat, obrigado! Você está absolutamente certo, quero dizer "possível" e "melhor ponto ...". Eu consertei minha pergunta.
Alex Golovnev 08/12/19
Quanto ao TSP métrico com ponto inicial e ponto final especificados, o melhor é que konwn é . Um artigo do STOC 2012 "Melhorando o algoritmo de Christofides para o st TSP de caminho" emarxiv.org/abs/1110.4604. 1+52
Peng Zhang

Respostas:

53

Estudei o problema e encontrei os algoritmos mais conhecidos para o TSP.

n é o número de vértices,M é o peso máximo da aresta. Todos os limites são dados acima para um factor polinomial do tamanho de entrada (poly(n,logM) ). Denotamos TSP assimétrico por ATSP.

1. Algoritmos Exatos para TSP

1.1 ATSP geral

M2nΩ(n/log(Mn))de tempo eexp-espaço (Björklund).

2n tempo e2n espaço (Bellman;Held, Karp).

4nnlogn tempo epoly -espaço (Gurevich, Sela;Björklund, Husfeldt).

22ntnlog(nt) tempo e2t espaço parat=n,n/2,n/4, (Koivisto, Parviainen).

O(Tn) tempo eO(Sn) espaço para qualquer2<S<2comTS<4(Koivisto, Parviainen).

2n×MTempo epoliespaço 2 n × M (Lokshtanov, Nederlof).

2n×M tempo e espaçoM (Kohn, Gottlieb, Kohn;Karp;Bax, Franklin).

2n

1.2 Casos Especiais de TSP

1.657n×M

(2ϵ)nϵ

(2ϵ)npolyϵ

1.251npoly

1.890npoly4

1.733n4

1.657npoly

(2ϵ)ndnd

2. Algoritmos de aproximação para TSP

2.1 TSP geral

Não pode ser aproximado em nenhuma função computável de tempo polinomial, a menos que P = NP ( Sahni, Gonzalez ).

2.2 TSP métrico

32

123122

2.3 TSP gráfico

75

2.4 (1,2) -TSP

MAX-SNP rígido ( Papadimitriou, Yannakakis ).

87

2.5 TSP em métricas com dimensão limitada

PTAS para TSP em um espaço euclidiano de dimensão fixa ( Arora ; Mitchell ).

logn

PTAS para TSP em métricas com dimensão de duplicação limitada ( Bartal, Gottlieb, Krauthgamer ).

2.6 ATSP com desigualdade de triângulo direcionado

O(1)

7574

2.7 TSP em gráficos com menores proibidos

PTAS de tempo linear ( Klein ) para TSP em gráficos planares.

PTAS para gráficos sem menores ( Demaine, Hajiaghayi, Kawarabayashi ).

2212

O(loggloglogg)g

2.8 MAX-TSP

79

78

34

3544

2.9 Aproximações de tempo exponencial

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

Ficaria muito grato por quaisquer adições e sugestões.

Alex Golovnev
fonte
5
Este é um ótimo resumo do que é conhecido. Recomendamos que você aceite esta resposta (mesmo que seja sua).
Suresh Venkat
1
Nitpick menor: você parece ter trocado de lugar para as constantes de inadequação para Metric TSP e ATSP.
22612 Michael Jackson é o nome de uma pessoa
2
Você pode adicionar gráficos planares / de gênero limitado / excluídos; os resultados que eu conheço são os seguintes. (1) TSP em gráficos planares - PTAS de tempo linear ( cs.brown.edu/people/klein/publications/no-contraction.pdf ), (2) TSP em gênero limitado / gráficos menores excluídos - QPTAS para gráficos não ponderados com menores excluídos / gráficos ponderados com gênero limitado ( cs.emory.edu/~mic/papers/15.pdf ), (3) ATSP em gráficos planares - aproximação fatorial constante ( stanford.edu/~saberi/atsp2.pdf ).
Zotachidil 6/07/12
4
@ Alex Golovnev: O algoritmo de Björklunds não funciona para o ATSP, mas depende crucialmente do gráfico ser simétrico.
Andreas Björklund
3
O resultado de Erickson-Sidiropoulos é para o ATSP - não está claro na lista acima. O PTAS de Arora funciona para qualquer dimensão fixa. Não gosto do termo "Metric 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: Esquemas de aproximação exponencial para alguns problemas gráficos. Disponível online .

Vincenzo
fonte
10

αβα<βγα,β]γθγ2nO(θ)γ(pelo menos na faixa de fatores constante), ver melhorias na taxa de aproximação, mesmo quando determinado o tempo subexponencial. Existem vários problemas em que o melhor resultado de dureza conhecido é através de uma redução ineficiente do SAT, ou seja, o resultado da dureza está sob uma suposição mais fraca, como NP não contida em tempo quase polinomial. Nesses casos, pode-se obter uma melhor aproximação no tempo subexponencial. O único que conheço é o problema da árvore do grupo Steiner. Um resultado famoso e recente é o de Arora-Barak-Steurer em um algoritmo de tempo subexponencial para jogos únicos: a conclusão que tiramos desse resultado é que, se UGC é verdadeiro, a redução de SAT para UGC deve ser algo que ineficiente, isto é, o tamanho da instância de UGC obtida a partir da fórmula SAT precisa crescer com os parâmetros de uma certa maneira.

Chandra Chekuri
fonte
2n
1

A melhor colher de chá para gráficos de gênero com limite ponderado é http://erikdemaine.org/papers/ContractionTSP_Combinatorica/ .

Convidado
fonte
obrigado, mas não é um caso especial do resultado Demaine-Hajiaghayi-Kawarabayashi apontado por Christian Sommer?
Alex Golovnev