Algoritmos de aproximación para TSP métrico

Se sabe que el TSP métrico se puede aproximar dentro de y no se puede aproximar mejor que $1.5$ en tiempo polinomial. ¿Se sabe algo sobre la búsqueda de soluciones de aproximación en tiempo exponencial (por ejemplo, menos de2npasos con solo espacio polinómico)? Por ejemplo, ¿en qué tiempo y espacio podemos encontrar un recorrido cuya distancia sea como máximo1.1×OPT?$123\over 122$$2^n$$1.1\times OPT$

He estudiado el problema y encontré los algoritmos más conocidos para TSP.

$n$ es el número de vértices,$M$ es el peso máximo del borde. Todos los límites se dan hasta un factor polinómico del tamaño de entrada ($poly(n, \log M)$ ). Denotamos TSP asimétrico por ATSP.

1. Algoritmos exactos para TSP

1.1. ATSP general

$M2^{n-\Omega(\sqrt{n/\log (Mn)})}$tiempo y$exp$-space (Björklund).

$2^n$ tiempo y$2^n$ espacio (Bellman;Held, Karp).

$4^n n^{\log n}$ tiempo y$poly$ -space (Gurevich, Sela;Björklund, Husfeldt).

$2^{2n-t} n^{\log(n-t)}$ tiempo y$2^t$ espacio para$t=n,n/2,n/4,\ldots$ (Koivisto, Parviainen).

$O^*(T^n)$ tiempo y$O^*(S^n)$ espacio para cualquier$\sqrt2<S<2$con$TS<4$(Koivisto, Parviainen).

$2^n\times M$ tiempo ypoliespacio(Lokshtanov, Nederlof).

$2^n\times M$ tiempo y espacio$M$ (Kohn, Gottlieb, Kohn;Karp;Bax, Franklin).

$2^n$

1.2. Casos especiales de TSP

$1.657^n\times M$

$(2-\epsilon)^n$$\epsilon$

$(2-\epsilon)^n$$poly$$\epsilon$

$1.251^n$$poly$

$1.890^n$$poly$$4$

$1.733^n$$4$

$1.657^n$$poly$

$(2-\epsilon)^n$$d^n$$d$

2. Algoritmos de aproximación para TSP

2.1. TSP general

No se puede aproximar dentro de ninguna función computable de tiempo polinomial a menos que P = NP ( Sahni, Gonzalez ).

2.2. TSP métrico

$3 \over 2$

$123\over 122$

2.3. TSP gráfico

$7\over5$

2.4. (1,2) -TSP

MAX-SNP duro ( Papadimitriou, Yannakakis ).

$8 \over 7$

2.5. TSP en métricas con dimensión acotada

PTAS para TSP en un espacio euclidiano de dimensión fija ( Arora ; Mitchell ).

$\log{n}$

PTAS para TSP en métricas con dimensión de duplicación acotada ( Bartal, Gottlieb, Krauthgamer ).

2.6. ATSP con desigualdad de triángulo dirigido

$O(1)$

$75\over 74$

2.7. TSP en gráficos con menores prohibidos

Tiempo lineal PTAS ( Klein ) para TSP en gráficos planos.

PTAS para gráficos sin menor ( Demaine, Hajiaghayi, Kawarabayashi ).

$22\frac{1}{2}$

$O(\frac{\log g}{\log\log g})$$g$

2.8. MAX-TSP

$7\over9$

$7\over8$

$3\over4$

$35\over44$

2.9. Aproximaciones de tiempo exponencial

$(1+\epsilon)$$2^{(1-\epsilon/2)n}$$\epsilon\le \frac{2}{5}$$4^{(1-\epsilon/2)n} n^{\log n}$$\epsilon \leq \frac{2}{3}$

Agradecería cualquier adición y sugerencia.

$O^*(1.932^n)$$O^*(2^n)$$n$$(1+\epsilon)$$O^*(2^{(1-\epsilon/2)n})$$\epsilon \le 2/5$

Nicolas Boria, Nicolas Bougeois, Bruno Escoffier, Vangelis Th. Paschos: esquemas de aproximación exponencial para algunos problemas gráficos. Disponible en linea .

$\alpha$$\beta$$\alpha < \beta$$\gamma$$\alpha, \beta]$$\gamma$$\theta$$\gamma$$2^{n^{O(\theta)}}$$\gamma$(al menos en el rango de factor constante) vea mejoras en la relación de aproximación incluso cuando se le da un tiempo sub-exponencial. Existen varios problemas en los que el mejor resultado de dureza conocido es a través de una reducción ineficiente de SAT, es decir, el resultado de dureza está bajo una suposición más débil, como NP no contenido en el tiempo cuasi polinomial. En tales casos, se puede obtener una mejor aproximación en el tiempo sub-exponencial. El único que conozco es el problema del árbol Steiner grupal. Un resultado famoso reciente es el de Arora-Barak-Steurer en un algoritmo de tiempo sub-exponencial para juegos únicos: la conclusión que sacamos de este resultado es que si UGC es cierto, entonces la reducción de SAT a UGC tiene que ser algo ineficiente, es decir, el tamaño de la instancia de UGC obtenida de la fórmula SAT tiene que crecer con los parámetros de cierta manera.

La mejor cucharadita para gráficos de género acotado ponderado es http://erikdemaine.org/papers/ContractionTSP_Combinatorica/ .