[Solved]: Why does this graph show the tightness of MST heuristic's 2-approximation bound?

Problem Detail: 

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?

Asked By : oarfish

Answered By : oarfish

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*} $

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/49462

 Ask a Question

 Download Related Notes/Documents