2
$\begingroup$

There is a problem I don't know the answer too. The 3 approximation for the bottleneck TSP that involves first getting the MST. I have not been able to come up with the right "shortcut" method so far.

To be more specific.

The problem comes from Cormen's Introduction to Algorithms 3rd edition . The problem is

In the bottleneck traveling-salesman problem, we wish to find the hamiltonian cycle that minimizes the cost of the most costly edge in the cycle. Assuming that the cost function satisfies the triangle inequality, show that there exists a polynomial time approximation algorithm with approximation ratio 3 for this problem. (Hint:Show recursively that we can visit all the nodes in a bottleneck spanning tree, as discussed in Problem 23-3, exactly once by taking a full walk of the tree and skipping nodes, but without skipping more than two consecutive intermediate nodes. Show that the costliest edge in a bottleneck spanning tree has a cost that is at most the cost of the costliest edge in a bottleneck hamiltonian cycle.)

I can prove that the MST is also a bottleneck spanning tree, however when I search online and Google scholar for the step where we walk on the bottleneck spanning tree, all of the articles are on much better approximations, and I can't seem to find any reference to this type of argument online.

$\endgroup$
0

1 Answer 1

1
$\begingroup$

You need to prove by induction the following claim:

Let $T$ be a tree rooted at $r$ with at least two vertices. You can list the vertices of $T$ in a sequence such that the distance (in $T$) between two adjacent vertices (including the first and the last) is at most $3$, and furthermore the vertex following $r$ is adjacent to $r$ (in $T$).

(The induction is on the number of vertices.)

Given this, you argue as follows. Suppose that there is a Hamiltonian cycle with heaviest edge having weight $w$. Then there is a spanning tree whose heaviest edge has weight $w$. So the heaviest edge in the bottleneck spanning tree has weight at most $w$. Apply the claim to that tree, and consider the corresponding Hamiltonian cycle. Since the tree distance between adjacent vertices is at most $3$ and thanks to the triangle inequality, the heaviest edge in the resulting cycles weighs at most $3w$.

$\endgroup$
3
  • $\begingroup$ In case you wondered, I will give no further hints on how to prove the claim. $\endgroup$ Sep 2, 2015 at 18:16
  • $\begingroup$ thanks yuval! think I got it after rooting the tree first. $\endgroup$
    – mmmi
    Sep 2, 2015 at 20:29
  • 1
    $\begingroup$ here's a result that may (or may not) give an alternative proof to the "you can list the vertices of $T$" claim: if $G$ is a connected graph, then $G^3$ has a Hamiltonian cycle. $\endgroup$
    – xdavidliu
    May 3, 2021 at 0:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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