7
$\begingroup$

Consider the following extremely simple approximation algorithm for the TSP.

Input: A complete weighted graph $G=(V,E).$

  1. Take any three vertices $a,b,c\in V$ and let $H:=(a,b,c,a).$
  2. While there are vertices in V that are not in H:

    1. Take one of them, say $v.$ Let $H=(v_1,v_2,...,v_k,v_1),$ where $k$ is the number of distinct vertices currently contained in $H.$
    2. Take as new $H$ the shortest of all the Hamiltonian cycles $(v,v_1,v_2,\ldots,v_k,v),$ $(v_1,v,v_2,\ldots,v_k,v_1),$ $(v_1,v_2,v,\ldots,v_k,v_1),$ $\dots,$ $(v_1,v_2,\ldots,v,v_k,v_1),$ i.e., insert $v$ before every vertex in $H$ and find the shortest Hamiltonian cycle among all those.

Output: $H.$

Obviously, this algorithm has runtime $O(n^2).$

Can anyone give me a lower (or upper) bound on the approximation ratio of this algorithm? Or a worst-case example, for that matter?

$\endgroup$
  • 1
    $\begingroup$ The question is definitely within scope. Try to state your algorithm more clearly (for example, what is k?), and use LaTeX code to help you with the math formulas. $\endgroup$ – Hsien-Chih Chang 張顯之 Dec 11 '10 at 7:50
  • $\begingroup$ Thank you for the tips! I wasn’t sure about the LaTeX because the preview only “switches” after a few seconds. $\endgroup$ – Sacha Dec 11 '10 at 8:14
  • $\begingroup$ @Sacha: You are welcome! The revision is nice, and it will make the question more readable, which increase the possibility that the question will be answered. A small typo: in the inner-loop, the cycles should be $(v,v_1,\ldots,v_k)$, $(v_1,v,\ldots,v_k)$ and so on, right? $\endgroup$ – Hsien-Chih Chang 張顯之 Dec 11 '10 at 8:19
  • $\begingroup$ I’m not sure what you mean. There was indeed a tiny typo in the definition of the first Hamiltonian cycle (it is of course $(v,v_1,v_2,\ldots,v_k,v)$ instead of $(v,v_1,v_2,\ldots,v_k,v_1)$). But I think our notation differs a little bit. What you write are paths to me—I think it’s just a matter of definition whether you include the last (first) vertex twice. $\endgroup$ – Sacha Dec 11 '10 at 8:24
  • $\begingroup$ I got you point, and you are right :) By writing $(v,v_1,\ldots,v_k)$, I do mean a cycle through all the nodes in it, which is the same as your notation $(v,v_1,\ldots,v_k,v)$. $\endgroup$ – Hsien-Chih Chang 張顯之 Dec 11 '10 at 8:30
9
$\begingroup$

General TSP is not approximable within any factor, so your algorithm doesn't really have a chance of working well. A worst-case example: We select one Hamiltonian cycle in the clique and give all its edges weight 1 (assume this cycle is $(v_1, v_2, ..., v_n, v_1)$. All the other edges have some big weight $\alpha(n)$. Now let's have your algorithm start with odd vertices. Between any odd vertices there are only edges with weight $\alpha(n)$ and we don't have any tie breaking rule, so the cycle on odd vertices your algorithm constructs can be totally arbitrary (we can for egample forbid it to contain any edges of the form $(v_i, v_{i+2})$. When the algorithm starts working on the even vertices, it will have just two possible places to put $v_i$: after $v_{i-1}$ or before $v_{i+1}$. Again we have no tie-breaking rule, so we can assume that it always choses to put $v_i$ after $v_{i-1}$ (of course we do all this modulo $n$). When we look at the constructed cycle, we see that it is built of alternating weight 1 and weight $\alpha(n)$ edges. So we have $OPT = n$, and our solution has weight ${n \over 2} + {\alpha(n) \over 2}$. We can chose $\alpha$ arbitrarily to disprove any claimed approximation factor. There are some technicalities involved with encoding weight $\alpha$; when we increase $\alpha$ the input size also grows (but more slowly), but still I think we can get any factor.

$\endgroup$
  • 5
    $\begingroup$ General TSP with the triangle inequality (which encompasses a large number of practical cases) is indeed approximable within a constant factor. $\endgroup$ – Peter Shor Dec 12 '10 at 1:52
25
$\begingroup$

This is called an insertion heuristic. The general TSP cannot be approximated unless $P=NP$. The question is more interesting for the metric TSP. In that case, Rosenkrantz et al. (1974) show that your heuristic gives an $O(\log n)$ approximation.

You can also try to choose a good vertex $v$ to be inserted in each step, instead of just taking an arbitrary one. One variant is farthest insertion in which $v$ is chosen such that is has maximum distance from the current $H$. Another variant is nearest insertion in which $v$ is chosen such that it has minimum distance from the current $H$. Yet another possibility is cheapest insertion in which $v$ is chosen such that the new $H$ has minimum length. Rosenkrantz et al. show that both nearest and cheapest insertion give a $2-2/n$ approximation and this is tight.

The full reference is: D. Rosenkrantz, R. Stearns, and P. Lewis II. An analysis of several heuristics for the traveling salesman problem. SIAM Journal on Computing, 6(3):563-581, 1977.

$\endgroup$
3
$\begingroup$

As proven here, general TSP is NPO-complete. This means you can either solve it exactly in exponential time or approximate it in polynomial time with an approximation factor growing exponentially with the length of the input. This means that your algorithm, when applied to general TSP instances, cannot give a better guarantee than a factor $O(2^{n^\epsilon})$ for some $\epsilon > 0$.

Different versions of TSP admit different bounds on approximation algorithms. For an overview, the site "A compendium of NP optimization problems" lists a number of TSP variants here. Wikipedia also gives a lot of bounds on its page about TSP, in this section and in this section.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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