HiveBrain v1.2.0
Get Started
← Back to all entries
gotchaMinor

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

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
thisshowwhythetightnessgraphapproximationboundheuristicmst

Problem

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?

Solution

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.

Context

StackExchange Computer Science Q#49462, answer score: 4

Revisions (0)

No revisions yet.