7
$\begingroup$

This is a homework problem I've been given and I've been raking my brain for hours (so I'm satisfied with some pointers). I know already that the approximation ratio cannot be worse than $2$. I have a wheel graph, where each edge has cost $1$ and the distance between all nodes which are not connected by edges is $2$. The wheel graph $W_6$ is this one:

I have marked in blue what I believe to be the output of an MST heuristic algorithm. But I also think this is the optimal solution, since all nodes can only be visited once. So the cost of the tour would be $7$ for both optimal and MST.

I do not see how this type of graph shows that the $2$-approximation bound of MST heuristic is tight (not necessarily this instance, but the graphs $W_n$ in general). Can someone enlighten me?

| cite | improve this question | |
$\endgroup$
  • 1
    $\begingroup$ No single example can "prove that the MST approximation to TSP is a 2-approximation", since being a 2-approximation requires being within a factor of two of optimal on all graphs. What this graph is supposed to do is prove that MST is not better than a 2-approximation, by showing a graph on which it's out by exactly a factor of two. By the way, there should presumably be a black edge from V1 to V6. $\endgroup$ – David Richerby Nov 14 '15 at 8:35
  • $\begingroup$ @DavidRicherby I know why it is no worse than a 2-approximation, this is supposed to be a worst-case instance showing the bound is tight. Or maybe a series of increasing n would have the ratio converge to two. And as far as I understand, the only black edges should be the spokes. Although having nodes in the circle connected with cost 1 does not change the tour I think. $\endgroup$ – oarfish Nov 14 '15 at 8:37
  • 1
    $\begingroup$ I suggest you rephrase your question to make that clear. $\endgroup$ – David Richerby Nov 14 '15 at 8:39
  • $\begingroup$ I do not see how this type of graph shows that the 2-approximation bound of MST heuristic is tight seems to make my intent clear. How would you suggest to edit the question? $\endgroup$ – oarfish Nov 14 '15 at 8:40
  • 2
    $\begingroup$ @oarfish The title is the biggest issue; it makes people expect a certain type of question. Then they read things that does not fit at all, they skip the rest and comment. $\endgroup$ – Raphael♦ Nov 14 '15 at 15:18
4
$\begingroup$

There is a lot of freedom in the algorithm: several minimum spanning trees, and several corresponding Eulerian tours. Try to find the worst choice and show that it produces an inferior tour. What you are showing is that the algorithm could make this choice, and so could produce an inferior approximation.

If you don't like this idea of choice, you can sometimes guarantee that the algorithm makes the choices you want by slightly tweaking the weights.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Where does the minimal matching come into play? I am not talking about Christofides, just MST heuristic. And as far as I can see and try on paper, it does not matter whether I start with the MST that is a star centred on $v_0$ or one that comprises the outer cycle minus one edge plus one of the spokes. Maybe I have a fundamental misunderstanding, but I think it is quite simple. $\endgroup$ – oarfish Nov 14 '15 at 14:43
  • $\begingroup$ @oarfish Right, Christofides' algorithm is actually better. $\endgroup$ – Yuval Filmus Nov 14 '15 at 16:15
  • $\begingroup$ I did not realise it before, but this is actually the right direction. One simply selects the worst possible tour. I did not see that there are many of them which are not equivalent when it comes to the generated TSP tour. $\endgroup$ – oarfish Nov 27 '15 at 11:40
3
$\begingroup$

The graph I posted is missing some edges, adjacent nodes in the cycle are supposed to be connected. (Edit: Fixed the graph with TSP tour).

The actual graph is this

My solution goes as follows. Now the MST computed for for the MST heuristic is obviously

allowing many euler tours, among others these ones:

where the cycle nodes can be visited in any order. Now any of the tours are valid so we can choose the worst one, for instance $v_0,v_4,v_0,v_1,v_0,v_3,v_0,v_6,v_0,v_2,v_0,v_5,v_0$. Based on that tour, MST heuristic finds this TSP solution:

Now since all edges have cost $1$ and and all nodes not connected in the graph have distance $2$, the cost of the tour is $2(n-1) + 2$ where the optimal tour would have cost $n+1$. In the limit

$\begin{equation*} \lim_{n\rightarrow\infty} \frac{MST(W_n)}{Opt(W_n)} = \lim_{n\rightarrow\infty}\frac{2n}{n+1} = 2 \end{equation*} $

| cite | improve this answer | |
$\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.