Approximation algorithms for Metric TSP
I've studied the problem and I found the best known algorithms for TSP.
$n$ is the number of vertices, $M$ is the maximal edge weight.
All bounds are given up to a polynomial factor of the input size ($poly(n, \log M)$).
We denote Asymmetric TSP by ATSP.
1. Exact Algorithms for TSP
1.1. General ATSP
$M2^{n-\Omega(\sqrt{n/\log (Mn)})}$ time and $exp$-space (Björklund).
$2^n$ time and $2^n$ space (Bellman; Held, Karp).
$4^n n^{\log n}$ time and $poly$-space (Gurevich, Shelah; Björklund, Husfeldt).
$2^{2n-t} n^{\log(n-t)}$ time and $2^t$ space for $t=n,n/2,n/4,\ldots$ (Koivisto, Parviainen).
$O^*(T^n)$ time and $O^*(S^n)$ space for any $\sqrt2&lt;S&lt;2$ with $TS&lt;4$ (Koivisto, Parviainen).
$2^n\times M$ time and poly-space (Lokshtanov, Nederlof).
$2^n\times M$ time and space $M$ (Kohn, Gottlieb, Kohn; Karp; Bax, Franklin).
Even for Metric TSP nothing better is known than algorithms above. It is a big challenge to develop $2^n$-time algorithm for TSP with polynomial space (see Open Problem 2.2.b, Woeginger).
1.2. Special Cases of TSP
$1.657^n\times M$ time and exponentially small probability of error(Björklund) for Undirected TSP.
$(2-\epsilon)^n$ and exponential space for TSP in graphs with bounded average degree, $\epsilon$ depends only on degree of graph (Cygan, Pilipczuk; Björklund, Kaski, Koutis).
$(2-\epsilon)^n$ and $poly$-space for TSP in graphs with bounded maximal degree and bounded integer weights, $\epsilon$ depends only on degree of graph (Björklund, Husfeldt, Kaski, Koivisto).
$1.251^n$ and $poly$-space for TSP in cubic graphs (Iwama, Nakashima).
$1.890^n$ and $poly$-space for TSP in graphs of degree $4$ (Eppstein).
$1.733^n$ and exponential space for TSP in graphs of degree $4$ (Gebauer).
$1.657^n$ time and $poly$-space for Undirected Hamiltomian Cycle (Björklund).
$(2-\epsilon)^n$ and exponential space for TSP in graphs with at most $d^n$ Hamiltonian cycles (for any constant $d$) (Björklund, Kaski, Koutis).
2. Approximation Algorithms for TSP
2.1. General TSP
Cannot be approximated within any polynomial time computable function unless P=NP (Sahni, Gonzalez).
2.2. Metric TSP
$3 \over 2$-approximation (Christofides).
Cannot be approximated with a ratio better than $123\over 122$ unless P=NP (Karpinski, Lampis, Schmied).
2.3. Graphic TSP
$7\over5$-approximation (Sebo, Vygen).
2.4. (1,2)-TSP
MAX-SNP hard (Papadimitriou, Yannakakis).
$8 \over 7$-approximation (Berman, Karpinski).
2.5. TSP in Metrics with Bounded Dimension
PTAS for TSP in a fixed-dimensional Euclidean space (Arora; Mitchell).
TSP is APX-hard in a $\log{n}$-dimensional Euclidean space (Trevisan).
PTAS for TSP in metrics with bounded doubling dimension (Bartal, Gottlieb, Krauthgamer).
2.6. ATSP with Directed Triangle Inequality
$O(1)$-approximation (Svensson, Tarnawski, Végh)
Cannot be approximated with a ratio better than $75\over 74$ unless P=NP (Karpinski, Lampis, Schmied).
2.7. TSP in Graphs with Forbidden Minors
Linear time PTAS (Klein) for TSP in Planar Graphs.
PTAS for minor-free graphs (Demaine, Hajiaghayi, Kawarabayashi).
$22\frac{1}{2}$-approximation for ATSP in planar graphs (Gharan, Saberi).
$O(\frac{\log g}{\log\log g})$-approximation for ATSP in genus-$g$ graphs (Erickson, Sidiropoulos).
2.8. MAX-TSP
$7\over9$-approximation for MAX-TSP (Paluch, Mucha, Madry).
$7\over8$-approximation for MAX-Metric-TSP (Kowalik, Mucha).
$3\over4$-approximation for MAX-ATSP (Paluch).
$35\over44$-approximation for MAX-Metric-ATSP (Kowalik, Mucha).
2.9. Exponential-Time Approximations
It is possible to compute $(1+\epsilon)$-approximation for MIN-Metric-TSP in time $2^{(1-\epsilon/2)n}$ with exponential space
for any $\epsilon\le \frac{2}{5}$, or in time $4^{(1-\epsilon/2)n} n^{\log n}$ with polynomial space for any $\epsilon \leq \frac{2}{3}$ (Boria, Bourgeois, Escoffier, Paschos).
I would be grateful for any additions and suggestions.