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:
- Take an optimal Steiner tree for $S$ of total weight $OPT$.
- Form an Euler cycle of this tree (of total weight $2OPT$).
- 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)$.
- Remove that edge to get a path of weight at most $(2-\frac{1}{n-1})OPT$.
- Keep only points from $S$ in the path and only the first occurence of each one.
- The triangle inequality guarantees that we got a path spanning $S$ of weight at most $(2-\frac{1}{n-1})OPT$.
- 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?)