<p>A 1.1-approximation can be obtained in time (and space) $O^*(1.932^n)$ by adapting a "truncated" version of Held and Karp's exact $O^*(2^n)$ algorithm. Here $n$ is the number of locations. More in general, a $(1+\epsilon)$-approximation can be found in time $O^*(2^{(1-\epsilon/2)n})$ for all $\epsilon \le 2/5$. This is from: </p>

<p>Nicolas Boria, Nicolas Bougeois, Bruno Escoffier, Vangelis Th. Paschos: Exponential approximation schemas for some graph problems. <a href="http://www.lamsade.dauphine.fr/~boria/papers/SteinerTSP.pdf">Available online</a>. </p>

CC BY-SA 3.0
2011-12-06T22:53:10.360Z
2011-12-06T22:53:10.360Z
Vincenzo
<p>A similar question can be asked for any problem where we have a lower bound $\alpha$ on the approximability and an upper bound $\beta$ and currently $\alpha &lt; \beta$. I am assuming that the questioner is interested in sub-exponential time algorithms. This depends on the unknown "truth". Say the problem is NP-Hard to approximate to within a factor $\gamma$ which is some where in the interval [$\alpha, \beta]$. What this means is that there is a reduction from SAT to the problem such that better than $\gamma$-approximation would allow us to decide the answer to SAT. If we believe the exponential-time hypothesis for SAT then the efficiency of the reduction will give a $\theta$ such that approximating below $\gamma$ is not possible in time less than $2^{n^{O(\theta)}}$. However any thing worse than $\gamma$ is possible in polynomial time. What this means is that we do not <em>typically</em> (at least in the constant factor range) see improvements in the approximation ratio even when given sub-exponential-time. There are several problems where the best hardness result known is via an inefficient reduction from SAT, that is, the hardness result is under a weaker assumption such as NP not contained in quasi-polynomial time. In such cases one may get a better approximation in sub-exponential time. The only one I know of is the group Steiner tree problem. A recent famous result is the one of Arora-Barak-Steurer on a sub-exponential-time algorithm for unique games: the conclusion we draw from this result is that if UGC is true then the reduction from SAT to UGC has to be some what inefficient, that is, the size of the instance of UGC obtained from the SAT formula has to grow with the parameters in a certain fashion. Of course this is predicated on the exponential-time hypothesis for SAT.</p>

CC BY-SA 3.0
2011-12-08T19:48:31.470Z
Thank you for the best explanation. In my opinion, it can be interesting to approximate TSP in time less than $2^n$. I meant not only sub-exponential algorithms. And you explained very well the situation with sub-exponential algorithms.
Alex Golovnev
CC BY-SA 3.0
2011-12-03T06:10:17.063Z
2011-12-03T06:10:17.063Z
Chandra Chekuri
<p>The best tsp for weighted bounded genus graphs is
<a href="http://erikdemaine.org/papers/ContractionTSP_Combinatorica/" rel="nofollow">http://erikdemaine.org/papers/ContractionTSP_Combinatorica/</a>.</p>

CC BY-SA 3.0
2013-05-12T05:52:37.557Z
thank you, but isn't it a special case of the Demaine-Hajiaghayi-Kawarabayashi result pointed out by Christian Sommer?
Alex Golovnev
CC BY-SA 3.0
2013-05-10T03:44:56.673Z
2013-05-10T06:13:43.433Z
2013-05-10T06:13:43.433Z
Guest
<p>I've studied the problem and I found the best known algorithms for TSP.</p>
<p><span class="math-container">$n$</span> is the number of vertices, <span class="math-container">$M$</span> is the maximal edge weight.
All bounds are given up to a polynomial factor of the input size (<span class="math-container">$poly(n, \log M)$</span>).
We denote Asymmetric TSP by ATSP.</p>
<h2>1. Exact Algorithms for TSP</h2>
<h3>1.1. General ATSP</h3>
<p><span class="math-container">$M2^{n-\Omega(\sqrt{n/\log (Mn)})}$</span> time and <span class="math-container">$exp$</span>-space (<a href="http://arxiv.org/pdf/1211.0391v2.pdf" rel="noreferrer">Björklund</a>).</p>
<p><span class="math-container">$2^n$</span> time and <span class="math-container">$2^n$</span> space (<a href="http://dl.acm.org/citation.cfm?id=321111" rel="noreferrer">Bellman</a>; <a href="http://epubs.siam.org/doi/pdf/10.1137/0110015" rel="noreferrer">Held, Karp</a>).</p>
<p><span class="math-container">$4^n n^{\log n}$</span> time and <span class="math-container">$poly$</span>-space (<a href="http://research.microsoft.com/en-us/um/people/gurevich/Opera/71.pdf" rel="noreferrer">Gurevich, Shelah</a>; <a href="http://www.springerlink.com/content/lp241v54q2854859/" rel="noreferrer">Björklund, Husfeldt</a>).</p>
<p><span class="math-container">$2^{2n-t} n^{\log(n-t)}$</span> time and <span class="math-container">$2^t$</span> space for <span class="math-container">$t=n,n/2,n/4,\ldots$</span> (<a href="http://dl.acm.org/citation.cfm?id=1873642" rel="noreferrer">Koivisto, Parviainen</a>).</p>
<p><span class="math-container">$O^*(T^n)$</span> time and <span class="math-container">$O^*(S^n)$</span> space for any <span class="math-container">$\sqrt2&lt;S&lt;2$</span> with <span class="math-container">$TS&lt;4$</span> (<a href="http://dl.acm.org/citation.cfm?id=1873642" rel="noreferrer">Koivisto, Parviainen</a>).</p>
<p><span class="math-container">$2^n\times M$</span> time and poly-space (<a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.192.3413&amp;rep=rep1&amp;type=pdf" rel="noreferrer">Lokshtanov, Nederlof</a>).</p>
<p><span class="math-container">$2^n\times M$</span> time and space <span class="math-container">$M$</span> (<a href="http://dl.acm.org/citation.cfm?id=810218" rel="noreferrer">Kohn, Gottlieb, Kohn</a>; <a href="http://www.sciencedirect.com/science/article/pii/016763778290044X" rel="noreferrer">Karp</a>; <a href="http://www.sciencedirect.com/science/article/pii/S0020019096001597" rel="noreferrer">Bax, Franklin</a>).</p>
<p>Even for Metric TSP nothing better is known than algorithms above. It is a big challenge to develop <span class="math-container">$2^n$</span>-time algorithm for TSP with polynomial space (see Open Problem 2.2.b, <a href="http://www.sciencedirect.com/science/article/pii/S0166218X0700128X" rel="noreferrer">Woeginger</a>).</p>
<h3>1.2. Special Cases of TSP</h3>
<p><span class="math-container">$1.657^n\times M$</span> time and exponentially small probability of error(<a href="http://dl.acm.org/citation.cfm?id=1918382" rel="noreferrer">Björklund</a>) for Undirected TSP.</p>
<p><span class="math-container">$(2-\epsilon)^n$</span> and exponential space for TSP in graphs with bounded average degree, <span class="math-container">$\epsilon$</span> depends only on degree of graph (<a href="http://arxiv.org/pdf/1302.3763v1.pdf" rel="noreferrer">Cygan, Pilipczuk</a>; <a href="https://arxiv.org/pdf/1607.04002.pdf" rel="noreferrer">Björklund, Kaski, Koutis</a>).</p>
<p><span class="math-container">$(2-\epsilon)^n$</span> and <span class="math-container">$poly$</span>-space for TSP in graphs with bounded maximal degree and bounded integer weights, <span class="math-container">$\epsilon$</span> depends only on degree of graph (<a href="http://www.springerlink.com/content/68x34k07762gp425/" rel="noreferrer">Björklund, Husfeldt, Kaski, Koivisto</a>).</p>
<p><span class="math-container">$1.251^n$</span> and <span class="math-container">$poly$</span>-space for TSP in cubic graphs (<a href="http://www.springerlink.com/content/qu47268n210j3nrr/" rel="noreferrer">Iwama, Nakashima</a>).</p>
<p><span class="math-container">$1.890^n$</span> and <span class="math-container">$poly$</span>-space for TSP in graphs of degree <span class="math-container">$4$</span> (<a href="http://www.springerlink.com/content/ae8vn6yh2ldtn2w0/" rel="noreferrer">Eppstein</a>).</p>
<p><span class="math-container">$1.733^n$</span> and exponential space for TSP in graphs of degree <span class="math-container">$4$</span> (<a href="http://www.siam.org/proceedings/analco/2008/anl08_023gebauerh.pdf" rel="noreferrer">Gebauer</a>).</p>
<p><span class="math-container">$1.657^n$</span> time and <span class="math-container">$poly$</span>-space for Undirected Hamiltomian Cycle (<a href="http://dl.acm.org/citation.cfm?id=1918382" rel="noreferrer">Björklund</a>).</p>
<p><span class="math-container">$(2-\epsilon)^n$</span> and exponential space for TSP in graphs with at most <span class="math-container">$d^n$</span> Hamiltonian cycles (for any constant <span class="math-container">$d$</span>) (<a href="https://arxiv.org/pdf/1607.04002.pdf" rel="noreferrer">Björklund, Kaski, Koutis</a>).</p>
<h2>2. Approximation Algorithms for TSP</h2>
<h3>2.1. General TSP</h3>
<p>Cannot be approximated within any polynomial time computable function unless P=NP (<a href="http://dl.acm.org/citation.cfm?id=321975" rel="noreferrer">Sahni, Gonzalez</a>).</p>
<h3>2.2. Metric TSP</h3>
<p><span class="math-container">$3 \over 2$</span>-approximation (<a href="http://en.wikipedia.org/wiki/Christofides_algorithm" rel="noreferrer">Christofides</a>).</p>
<p>Cannot be approximated with a ratio better than <span class="math-container">$123\over 122$</span> unless P=NP (<a href="http://arxiv.org/pdf/1303.6437v1.pdf" rel="noreferrer">Karpinski, Lampis, Schmied</a>).</p>
<h3>2.3. Graphic TSP</h3>
<p><span class="math-container">$7\over5$</span>-approximation (<a href="http://arxiv.org/pdf/1201.1870.pdf" rel="noreferrer">Sebo, Vygen</a>).</p>
<h3>2.4. (1,2)-TSP</h3>
<p>MAX-SNP hard (<a href="http://www.jstor.org/discover/10.2307/3690150?uid=3738936&amp;uid=2&amp;uid=4&amp;sid=56204759503" rel="noreferrer">Papadimitriou, Yannakakis</a>).</p>
<p><span class="math-container">$8 \over 7$</span>-approximation (<a href="http://dl.acm.org/citation.cfm?id=1109627" rel="noreferrer">Berman, Karpinski</a>).</p>
<h3>2.5. TSP in Metrics with Bounded Dimension</h3>
<p>PTAS for TSP in a fixed-dimensional Euclidean space (<a href="http://dl.acm.org/citation.cfm?id=796342" rel="noreferrer">Arora</a>; <a href="http://dl.acm.org/citation.cfm?id=312204" rel="noreferrer">Mitchell</a>).</p>
<p>TSP is APX-hard in a <span class="math-container">$\log{n}$</span>-dimensional Euclidean space (<a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.53.6336&amp;rep=rep1&amp;type=pdf" rel="noreferrer">Trevisan</a>).</p>
<p>PTAS for TSP in metrics with bounded doubling dimension (<a href="http://arxiv.org/pdf/1112.0699.pdf" rel="noreferrer">Bartal, Gottlieb, Krauthgamer</a>).</p>
<h3>2.6. ATSP with Directed Triangle Inequality</h3>
<p><span class="math-container">$O(1)$</span>-approximation (<a href="https://arxiv.org/pdf/1708.04215.pdf" rel="noreferrer">Svensson, Tarnawski, Végh</a>)</p>
<p>Cannot be approximated with a ratio better than <span class="math-container">$75\over 74$</span> unless P=NP (<a href="http://arxiv.org/pdf/1303.6437v1.pdf" rel="noreferrer">Karpinski, Lampis, Schmied</a>).</p>
<h3>2.7. TSP in Graphs with Forbidden Minors</h3>
<p>Linear time PTAS (<a href="http://www.cs.brown.edu/people/klein/publications/no-contraction.pdf" rel="noreferrer">Klein</a>) for TSP in Planar Graphs.</p>
<p>PTAS for minor-free graphs (<a href="http://erikdemaine.org/papers/ContractionMinorFree_STOC2011/paper.pdf" rel="noreferrer">Demaine, Hajiaghayi, Kawarabayashi</a>).</p>
<p><span class="math-container">$22\frac{1}{2}$</span>-approximation for ATSP in planar graphs (<a href="http://www.stanford.edu/%7Esaberi/atsp2.pdf" rel="noreferrer">Gharan, Saberi</a>).</p>
<p><span class="math-container">$O(\frac{\log g}{\log\log g})$</span>-approximation for ATSP in genus-<span class="math-container">$g$</span> graphs (<a href="http://www.cs.uiuc.edu/%7Ejeffe/pubs/pdf/atsp.pdf" rel="noreferrer">Erickson, Sidiropoulos</a>).</p>
<h3>2.8. MAX-TSP</h3>
<p><span class="math-container">$7\over9$</span>-approximation for MAX-TSP (<a href="http://arxiv.org/pdf/0812.5101.pdf" rel="noreferrer">Paluch, Mucha, Madry</a>).</p>
<p><span class="math-container">$7\over8$</span>-approximation for MAX-Metric-TSP (<a href="http://duch.mimuw.edu.pl/%7Emucha/pub/approx08.pdf" rel="noreferrer">Kowalik, Mucha</a>).</p>
<p><span class="math-container">$3\over4$</span>-approximation for MAX-ATSP (<a href="http://arxiv.org/pdf/1401.3670v1.pdf" rel="noreferrer">Paluch</a>).</p>
<p><span class="math-container">$35\over44$</span>-approximation for MAX-Metric-ATSP (<a href="http://www.mimuw.edu.pl/%7Emucha/pub/wads07-max-tsp.pdf" rel="noreferrer">Kowalik, Mucha</a>).</p>
<h3>2.9. Exponential-Time Approximations</h3>
<p>It is possible to compute <span class="math-container">$(1+\epsilon)$</span>-approximation for MIN-Metric-TSP in time <span class="math-container">$2^{(1-\epsilon/2)n}$</span> with exponential space
for any <span class="math-container">$\epsilon\le \frac{2}{5}$</span>, or in time <span class="math-container">$4^{(1-\epsilon/2)n} n^{\log n}$</span> with polynomial space for any <span class="math-container">$\epsilon \leq \frac{2}{3}$</span> (<a href="http://www.lamsade.dauphine.fr/%7Eboria/papers/SteinerTSP.pdf" rel="noreferrer">Boria, Bourgeois, Escoffier, Paschos</a>).</p>
<p>I would be grateful for any additions and suggestions.</p>

CC BY-SA 3.0
2012-05-27T20:23:44.083Z
This is a great summary of what's known. I'd encourage you to accept this answer (even though it's your own).
Suresh Venkat
CC BY-SA 3.0
2012-07-03T19:19:50.760Z
Minor nitpick: you seem to have switched places for the inapproximability constants for Metric TSP and ATSP.
Michael Lampis
CC BY-SA 3.0
2012-07-06T01:23:12.097Z
You could add planar/bounded genus/excluded minor graphs; the results I'm aware of are as follows. (1) TSP in planar graphs - linear time PTAS (http://www.cs.brown.edu/people/klein/publications/no-contraction.pdf), (2) TSP in bounded genus/excluded minor graphs - QPTAS for unweighted graphs with excluded minors/weighted graphs with bounded genus (http://www.cs.emory.edu/~mic/papers/15.pdf), (3) ATSP in planar graphs - constant factor approximation (http://www.stanford.edu/~saberi/atsp2.pdf).
zotachidil
CC BY-SA 3.0
2012-07-08T07:53:46.493Z
@Alex Golovnev: Björklunds algorithm does not work for ATSP, it depends crucially on the graph being symmetric.
Andreas Björklund
CC BY-SA 3.0
2013-05-07T16:27:45.273Z
Metric ATSP on genus g graphs can be approximated within $O(\log g/ \log\log g)$ factor by a reduction to a general metric ATSP problem with $O(g)$ nodes.  http://www.cs.uiuc.edu/~jeffe/pubs/pdf/atsp.pdf
Hsien-Chih Chang 張顯之
CC BY-SA 3.0
2013-05-07T21:14:00.157Z
@Hsien-ChihChang張顯之, thank you, added!
Alex Golovnev
CC BY-SA 3.0
2013-05-07T22:40:00.497Z
The result of Erickson-Sidiropoulos is for ATSP - it is not clear in the list above. The PTAS of Arora works for any fixed dimension. I don't like the term "Metric ATSP".
Chandra Chekuri
CC BY-SA 3.0
2013-05-08T01:19:28.363Z
PTAS for minor-free graphs: Demaine, Hajiaghayi, Kawarabayashi: http://erikdemaine.org/papers/ContractionMinorFree_STOC2011/
Christian Sommer
CC BY-SA 3.0
2013-05-08T17:02:29.177Z
There is a PTAS for bounded doubling dimension, extending Arora/Mitchell: http://dl.acm.org/citation.cfm?id=2214038. In $\log n$ dimensions Euclidean TSP is APX-hard (Trevisan, "From Hamming to Euclid"). It may be good to point out the hardness -together with the doubling dimension result, it shows that what makes the problem easier is the low dimensionality, not anything special about Euclidean geometry.
Sasho Nikolov
CC BY-SA 3.0
2013-05-12T05:46:46.393Z
ChandraChekuri, ChristianSommer, SashoNikolov, thanks a lot! Could you please suggest other short name for ATSP satisfying the triangle inequality?
Alex Golovnev
CC BY-SA 3.0
2013-05-12T17:47:50.227Z
Some questions and answers like this, are deserves to get multiple upvotes.
Saeed
CC BY-SA 3.0
2013-08-24T20:18:09.260Z
@AlexGolovnev you have the wrong link for Held-Karp. [This is the correct paper](http://epubs.siam.org/doi/pdf/10.1137/0110015).
Austin Buchanan
CC BY-SA 4.0
2012-05-26T21:30:46.990Z
2019-01-25T03:01:50.353Z
2020-06-17T09:38:08.363Z
Alex Golovnev
<p>It is known that metric TSP can be approximated within $1.5$ and cannot be approximated better than $123\over 122$ in polynomial time. 
Is anything known about finding approximation solutions in exponential time (for example, less than $2^n$ steps with only polynomial space)? 
E.g. in what time and space we can find a tour whose distance is at most $1.1\times OPT$?</p>

CC BY-SA 3.0
2011-12-02T08:31:45.330Z
A natural approach in addressing questions of this type is to look at linear programming hierarchies such as Sherali-Adams, Lovász-Schrijver, or Lasserre, that allow running time $poly(n^r)$ at the $r$th level (and usually increasingly better approximations as $r$ grows). However I'm not aware of any positive or negative results about applicability of hierarchies on the LP relaxation of metric TSP (known as Held-Karp).
Mahdi Cheraghchi
CC BY-SA 3.0
2011-12-02T16:24:03.547Z
You probably mean "possible" rather than "needed" ? Also, I'm not sure what you mean by finding solutions in exponential time, since I can always find the exact answer. I assume you mean "find better points on the approximation/complexity tradeoff curve" ?
Suresh Venkat
CC BY-SA 3.0
2011-12-08T19:12:19.990Z
@MCH, thank you very much, but I have not found any results.
Alex Golovnev
CC BY-SA 3.0
2011-12-08T19:16:25.463Z
@Suresh Venkat, thank you! You are absolutely right, I mean "possible" and "better point...". I fixed my question.
Alex Golovnev
CC BY-SA 3.0
2012-05-28T07:52:39.007Z
As for the Metric TSP with specified starting point and ending point, the best is konwn is $\frac{1+\sqrt{5}}{2}$. A STOC 2012 paper "Improving Christofides’ Algorithm for the s-t Path TSP" at http://arxiv.org/abs/1110.4604.
Peng Zhang
CC BY-SA 4.0
2021-02-14T13:40:26.290Z
Hi there. I don't understand how can someone could prove that "[TSP] cannot be approximated better than 123/122 in polynomial time", when it is still unknown whether P=NP or not. TSP is proved to be NP-complete. What is the reference for this result please? The first reference I found (https://www.golovnev.org/papers/tsp.pdf) is very careful and says ", unless P=NP". I think this question should be updated to state this too. Thanks.
Næreen
<cc.complexity-theory><graph-algorithms><approximation-algorithms><tsp><exp-time-algorithms>
Approximation algorithms for Metric TSP
Alex Golovnev
# Approximation algorithms for Metric TSP

(Asked by: username_0 on 2011-12-02)

It is known that metric TSP can be approximated within $1.5$ and cannot be approximated better than $123\over 122$ in polynomial time.
Is anything known about finding approximation solutions in exponential time (for example, less than $2^n$ steps with only polynomial space)?
E.g. in what time and space we can find a tour whose distance is at most $1.1\times OPT$?

**Tags:** cc.complexity-theory, graph-algorithms, approximation-algorithms, tsp, exp-time-algorithms

> **Comments:**
> **username_1**: A natural approach in addressing questions of this type is to look at linear programming hierarchies such as Sherali-Adams, Lovász-Schrijver, or Lasserre, that allow running time $poly(n^r)$ at the $r$th level (and usually increasingly better approximations as $r$ grows). However I'm not aware of any positive or negative results about applicability of hierarchies on the LP relaxation of metric TSP (known as Held-Karp).  
> **username_2**: You probably mean "possible" rather than "needed" ? Also, I'm not sure what you mean by finding solutions in exponential time, since I can always find the exact answer. I assume you mean "find better points on the approximation/complexity tradeoff curve" ?  
> **username_0**: @MCH, thank you very much, but I have not found any results.  
> **username_0**: @username_2, thank you! You are absolutely right, I mean "possible" and "better point...". I fixed my question.  
> **username_3**: As for the Metric TSP with specified starting point and ending point, the best is konwn is $\frac{1+\sqrt{5}}{2}$. A STOC 2012 paper "Improving Christofides’ Algorithm for the s-t Path TSP" at http://arxiv.org/abs/1110.4604.  
> **username_4**: Hi there. I don't understand how can someone could prove that "[TSP] cannot be approximated better than 123/122 in polynomial time", when it is still unknown whether P=NP or not. TSP is proved to be NP-complete. What is the reference for this result please? The first reference I found (https://www.golovnev.org/papers/tsp.pdf) is very careful and says ", unless P=NP". I think this question should be updated to state this too. Thanks.  

---

## 4 answers

### Answer by username_0 on 2012-05-26. Score: 61 | Accepted answer

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](http://arxiv.org/pdf/1211.0391v2.pdf)).

$2^n$ time and $2^n$ space ([Bellman](http://dl.acm.org/citation.cfm?id=321111); [Held, Karp](http://epubs.siam.org/doi/pdf/10.1137/0110015)).

$4^n n^{\log n}$ time and $poly$-space ([Gurevich, Shelah](http://research.microsoft.com/en-us/um/people/gurevich/Opera/71.pdf); [Björklund, Husfeldt](http://www.springerlink.com/content/lp241v54q2854859/)).

$2^{2n-t} n^{\log(n-t)}$ time and $2^t$ space for $t=n,n/2,n/4,\ldots$ ([Koivisto, Parviainen](http://dl.acm.org/citation.cfm?id=1873642)).

$O^\*(T^n)$ time and $O^\*(S^n)$ space for any $\sqrt2 with $TS<4$ ([Koivisto, Parviainen](http://dl.acm.org/citation.cfm?id=1873642)).

$2^n\times M$ time and poly-space ([Lokshtanov, Nederlof](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.192.3413&rep=rep1&type=pdf)).

$2^n\times M$ time and space $M$ ([Kohn, Gottlieb, Kohn](http://dl.acm.org/citation.cfm?id=810218); [Karp](http://www.sciencedirect.com/science/article/pii/016763778290044X); [Bax, Franklin](http://www.sciencedirect.com/science/article/pii/S0020019096001597)).

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](http://www.sciencedirect.com/science/article/pii/S0166218X0700128X)).

### 1.2. Special Cases of TSP

$1.657^n\times M$ time and exponentially small probability of error([Björklund](http://dl.acm.org/citation.cfm?id=1918382)) 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](http://arxiv.org/pdf/1302.3763v1.pdf); [Björklund, Kaski, Koutis](https://arxiv.org/pdf/1607.04002.pdf)).

$(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](http://www.springerlink.com/content/68x34k07762gp425/)).

$1.251^n$ and $poly$-space for TSP in cubic graphs ([Iwama, Nakashima](http://www.springerlink.com/content/qu47268n210j3nrr/)).

$1.890^n$ and $poly$-space for TSP in graphs of degree $4$ ([Eppstein](http://www.springerlink.com/content/ae8vn6yh2ldtn2w0/)).

$1.733^n$ and exponential space for TSP in graphs of degree $4$ ([Gebauer](http://www.siam.org/proceedings/analco/2008/anl08_023gebauerh.pdf)).

$1.657^n$ time and $poly$-space for Undirected Hamiltomian Cycle ([Björklund](http://dl.acm.org/citation.cfm?id=1918382)).

$(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](https://arxiv.org/pdf/1607.04002.pdf)).

## 2. Approximation Algorithms for TSP

### 2.1. General TSP

Cannot be approximated within any polynomial time computable function unless P=NP ([Sahni, Gonzalez](http://dl.acm.org/citation.cfm?id=321975)).

### 2.2. Metric TSP

$3 \over 2$-approximation ([Christofides](http://en.wikipedia.org/wiki/Christofides_algorithm)).

Cannot be approximated with a ratio better than $123\over 122$ unless P=NP ([Karpinski, Lampis, Schmied](http://arxiv.org/pdf/1303.6437v1.pdf)).

### 2.3. Graphic TSP

$7\over5$-approximation ([Sebo, Vygen](http://arxiv.org/pdf/1201.1870.pdf)).

### 2.4. (1,2)-TSP

MAX-SNP hard ([Papadimitriou, Yannakakis](http://www.jstor.org/discover/10.2307/3690150?uid=3738936&uid=2&uid=4&sid=56204759503)).

$8 \over 7$-approximation ([Berman, Karpinski](http://dl.acm.org/citation.cfm?id=1109627)).

### 2.5. TSP in Metrics with Bounded Dimension

PTAS for TSP in a fixed-dimensional Euclidean space ([Arora](http://dl.acm.org/citation.cfm?id=796342); [Mitchell](http://dl.acm.org/citation.cfm?id=312204)).

TSP is APX-hard in a $\log{n}$-dimensional Euclidean space ([Trevisan](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.53.6336&rep=rep1&type=pdf)).

PTAS for TSP in metrics with bounded doubling dimension ([Bartal, Gottlieb, Krauthgamer](http://arxiv.org/pdf/1112.0699.pdf)).

### 2.6. ATSP with Directed Triangle Inequality

$O(1)$-approximation ([Svensson, Tarnawski, Végh](https://arxiv.org/pdf/1708.04215.pdf))

Cannot be approximated with a ratio better than $75\over 74$ unless P=NP ([Karpinski, Lampis, Schmied](http://arxiv.org/pdf/1303.6437v1.pdf)).

### 2.7. TSP in Graphs with Forbidden Minors

Linear time PTAS ([Klein](http://www.cs.brown.edu/people/klein/publications/no-contraction.pdf)) for TSP in Planar Graphs.

PTAS for minor-free graphs ([Demaine, Hajiaghayi, Kawarabayashi](http://erikdemaine.org/papers/ContractionMinorFree_STOC2011/paper.pdf)).

$22\frac{1}{2}$-approximation for ATSP in planar graphs ([Gharan, Saberi](http://www.stanford.edu/%7Esaberi/atsp2.pdf)).

$O(\frac{\log g}{\log\log g})$-approximation for ATSP in genus-$g$ graphs ([Erickson, Sidiropoulos](http://www.cs.uiuc.edu/%7Ejeffe/pubs/pdf/atsp.pdf)).

### 2.8. MAX-TSP

$7\over9$-approximation for MAX-TSP ([Paluch, Mucha, Madry](http://arxiv.org/pdf/0812.5101.pdf)).

$7\over8$-approximation for MAX-Metric-TSP ([Kowalik, Mucha](http://duch.mimuw.edu.pl/%7Emucha/pub/approx08.pdf)).

$3\over4$-approximation for MAX-ATSP ([Paluch](http://arxiv.org/pdf/1401.3670v1.pdf)).

$35\over44$-approximation for MAX-Metric-ATSP ([Kowalik, Mucha](http://www.mimuw.edu.pl/%7Emucha/pub/wads07-max-tsp.pdf)).

### 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](http://www.lamsade.dauphine.fr/%7Eboria/papers/SteinerTSP.pdf)).

I would be grateful for any additions and suggestions.

> **Comments:**
> **username_2**: This is a great summary of what's known. I'd encourage you to accept this answer (even though it's your own).  
> **username_8**: Minor nitpick: you seem to have switched places for the inapproximability constants for Metric TSP and ATSP.  
> **username_9**: You could add planar/bounded genus/excluded minor graphs; the results I'm aware of are as follows. (1) TSP in planar graphs - linear time PTAS (http://www.cs.brown.edu/people/klein/publications/no-contraction.pdf), (2) TSP in bounded genus/excluded minor graphs - QPTAS for unweighted graphs with excluded minors/weighted graphs with bounded genus (http://www.cs.emory.edu/~mic/papers/15.pdf), (3) ATSP in planar graphs - constant factor approximation (http://www.stanford.edu/~saberi/atsp2.pdf).  
> **username_10**: @username_0: Björklunds algorithm does not work for ATSP, it depends crucially on the graph being symmetric.  
> **username_11**: Metric ATSP on genus g graphs can be approximated within $O(\log g/ \log\log g)$ factor by a reduction to a general metric ATSP problem with $O(g)$ nodes.  http://www.cs.uiuc.edu/~jeffe/pubs/pdf/atsp.pdf  
> **username_0**: @Hsien-ChihChang張顯之, thank you, added!  
> **username_6**: The result of Erickson-Sidiropoulos is for ATSP - it is not clear in the list above. The PTAS of Arora works for any fixed dimension. I don't like the term "Metric ATSP".  
> **username_12**: PTAS for minor-free graphs: Demaine, Hajiaghayi, Kawarabayashi: http://erikdemaine.org/papers/ContractionMinorFree_STOC2011/  
> **username_13**: There is a PTAS for bounded doubling dimension, extending Arora/Mitchell: http://dl.acm.org/citation.cfm?id=2214038. In $\log n$ dimensions Euclidean TSP is APX-hard (Trevisan, "From Hamming to Euclid"). It may be good to point out the hardness -together with the doubling dimension result, it shows that what makes the problem easier is the low dimensionality, not anything special about Euclidean geometry.  
> **username_0**: ChandraChekuri, ChristianSommer, SashoNikolov, thanks a lot! Could you please suggest other short name for ATSP satisfying the triangle inequality?  
> **username_14**: Some questions and answers like this, are deserves to get multiple upvotes.  
> **username_15**: @AlexGolovnev you have the wrong link for Held-Karp. [This is the correct paper](http://epubs.siam.org/doi/pdf/10.1137/0110015).  

---

### Answer by username_5 on 2011-12-06. Score: 27

A 1.1-approximation can be obtained in time (and space) $O^\*(1.932^n)$ by adapting a "truncated" version of Held and Karp's exact $O^\*(2^n)$ algorithm. Here $n$ is the number of locations. More in general, a $(1+\epsilon)$-approximation can be found in time $O^\*(2^{(1-\epsilon/2)n})$ for all $\epsilon \le 2/5$. This is from:

Nicolas Boria, Nicolas Bougeois, Bruno Escoffier, Vangelis Th. Paschos: Exponential approximation schemas for some graph problems. [Available online](http://www.lamsade.dauphine.fr/~boria/papers/SteinerTSP.pdf).


---

### Answer by username_6 on 2011-12-03. Score: 10

A similar question can be asked for any problem where we have a lower bound $\alpha$ on the approximability and an upper bound $\beta$ and currently $\alpha < \beta$. I am assuming that the questioner is interested in sub-exponential time algorithms. This depends on the unknown "truth". Say the problem is NP-Hard to approximate to within a factor $\gamma$ which is some where in the interval [$\alpha, \beta]$. What this means is that there is a reduction from SAT to the problem such that better than $\gamma$-approximation would allow us to decide the answer to SAT. If we believe the exponential-time hypothesis for SAT then the efficiency of the reduction will give a $\theta$ such that approximating below $\gamma$ is not possible in time less than $2^{n^{O(\theta)}}$. However any thing worse than $\gamma$ is possible in polynomial time. What this means is that we do not *typically* (at least in the constant factor range) see improvements in the approximation ratio even when given sub-exponential-time. There are several problems where the best hardness result known is via an inefficient reduction from SAT, that is, the hardness result is under a weaker assumption such as NP not contained in quasi-polynomial time. In such cases one may get a better approximation in sub-exponential time. The only one I know of is the group Steiner tree problem. A recent famous result is the one of Arora-Barak-Steurer on a sub-exponential-time algorithm for unique games: the conclusion we draw from this result is that if UGC is true then the reduction from SAT to UGC has to be some what inefficient, that is, the size of the instance of UGC obtained from the SAT formula has to grow with the parameters in a certain fashion. Of course this is predicated on the exponential-time hypothesis for SAT.

> **Comments:**
> **username_0**: Thank you for the best explanation. In my opinion, it can be interesting to approximate TSP in time less than $2^n$. I meant not only sub-exponential algorithms. And you explained very well the situation with sub-exponential algorithms.  

---

### Answer by username_7 on 2013-05-10. Score: 1

The best tsp for weighted bounded genus graphs is
<http://erikdemaine.org/papers/ContractionTSP_Combinatorica/>.

> **Comments:**
> **username_0**: thank you, but isn't it a special case of the Demaine-Hajiaghayi-Kawarabayashi result pointed out by username_12?  

---

