Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

My question is about a subtlety regarding the $2$-approximation for the Metric Steiner Tree problem.

The classical Metric Steiner tree problem:

Given a metric space on $n$ points and a subset $S$ of the points, find a tree that spans $S$ with minimal total cost.

The classical $(2-\frac{1}{n-1})$-approximation:

Take a minimal spanning tree on the subraph induced on $S$.

Why it is a $(2-\frac{1}{n-1})$-approximation:

  1. Take an optimal Steiner tree for $S$ of total weight $OPT$.
  2. Form an Euler cycle of this tree (of total weight $2OPT$).
  3. This cycle contains at most $2(n-1)$ edges (counted with multiplicity), and thus it has an edge of weight no less than $(2OPT)/(2(n-1)) = OPT/(n-1)$.
  4. Remove that edge to get a path of weight at most $(2-\frac{1}{n-1})OPT$.
  5. Keep only points from $S$ in the path and only the first occurence of each one.
  6. The triangle inequality guarantees that we got a path spanning $S$ of weight at most $(2-\frac{1}{n-1})OPT$.
  7. Since a path is a special case of a tree, the weight of the minimal spanning tree is at most $(2-\frac{1}{n-1})OPT$.

On the other hand, this approximation algorithm is not much better than our analysis shows because if we take $S$ to be a a set of $n-1$ points, each pair is $2$ distance units apart, and add a single point not in $S$, at distance $1$ from each point in $S$, then, there is a Steiner tree of weight $n-1$, but the algorithm would return a tree of weight $2(n-2)$. This gives a ratio of $\frac{2(n-2)}{n-1}=2-\frac{2}{n-1}$.

My question:

Can we close the gap between $2-\frac{1}{n-1}$ and $2-\frac{2}{n-1}$? (that is, for this specific approximation algorithm, what is the true ratio?)

share|improve this question
    
It's $2-\frac{2}{n-1}$. –  Elena May 11 '12 at 14:02
    
If $S=V$ then we get a ratio of $1$. If $V \neq S$, then by removing the edge only after step 5, we get the desired inequality. –  Elena May 11 '12 at 14:04
    
(I don't have sufficient reputation to answer my own question) –  Elena May 11 '12 at 14:05
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.