Sabe-se que o TSP métrico pode ser aproximado dentro de e não pode ser aproximado melhor que 123 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?
cc.complexity-theory
graph-algorithms
approximation-algorithms
tsp
exp-time-algorithms
Alex Golovnev
fonte
fonte
Respostas:
Estudei o problema e encontrei os algoritmos mais conhecidos para o TSP.
1. Algoritmos Exatos para TSP
1.1 ATSP geral
1.2 Casos Especiais de TSP
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
2.3 TSP gráfico
2.4 (1,2) -TSP
MAX-SNP rígido ( Papadimitriou, Yannakakis ).
2.5 TSP em métricas com dimensão limitada
PTAS para TSP em um espaço euclidiano de dimensão fixa ( Arora ; Mitchell ).
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
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 ).
2.8 MAX-TSP
2.9 Aproximações de tempo exponencial
Ficaria muito grato por quaisquer adições e sugestões.
fonte
Nicolas Boria, Nicolas Bougeois, Bruno Escoffier, Vangelis Th. Paschos: Esquemas de aproximação exponencial para alguns problemas gráficos. Disponível online .
fonte
fonte
A melhor colher de chá para gráficos de gênero com limite ponderado é http://erikdemaine.org/papers/ContractionTSP_Combinatorica/ .
fonte