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$?

  • 3
    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). – MCH Dec 2 '11 at 8:31
  • 3
    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 Dec 2 '11 at 16:24
  • @MCH, thank you very much, but I have not found any results. – Alex Golovnev Dec 8 '11 at 19:12
  • @Suresh Venkat, thank you! You are absolutely right, I mean "possible" and "better point...". I fixed my question. – Alex Golovnev Dec 8 '11 at 19:16
  • 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 arxiv.org/abs/1110.4604. – Peng Zhang May 28 '12 at 7:52
up vote 49 down vote accepted

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<S<2$ with $TS<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).

$(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. 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(\frac{\log n}{\log\log n})$-approximation (Asadpour, Goemans, Madry, Gharan, Saberi).

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.

  • 5
    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 May 27 '12 at 20:23
  • 1
    Minor nitpick: you seem to have switched places for the inapproximability constants for Metric TSP and ATSP. – Michael Lampis Jul 3 '12 at 19:19
  • 2
    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 (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 (cs.emory.edu/~mic/papers/15.pdf), (3) ATSP in planar graphs - constant factor approximation (stanford.edu/~saberi/atsp2.pdf). – zotachidil Jul 6 '12 at 1:23
  • 4
    @Alex Golovnev: Björklunds algorithm does not work for ATSP, it depends crucially on the graph being symmetric. – Andreas Björklund Jul 8 '12 at 7:53
  • 3
    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 May 7 '13 at 22:40

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.

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.

  • 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 Dec 8 '11 at 19:48

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

  • thank you, but isn't it a special case of the Demaine-Hajiaghayi-Kawarabayashi result pointed out by Christian Sommer? – Alex Golovnev May 12 '13 at 5:52

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.