Metric Steiner Tree Problem

• INSTANCE: A finite metric space $(V,d)$ and set of terminals $S\subseteq V$ .
• SOLUTION: A tree $T=(V_{T}, E_{T})$ such that $S \subseteq V_{T} \subseteq V$ .
• COST FUNCTION: $\sum_{e=\{ u,v\} \in E_{T} } d(u,v)$ .
• OBJECTIVE: Minimize. within $\ln{4}+\epsilon < 1.39$ [21] (see also [98],[73]).
• Hardness: NP-hard to approximate within an approximation ratio 96/95 [36].
• Comment: Metric Steiner Tree is equivalent to Minimum Steiner Tree.