- INSTANCE: Graph , cost function , set of terminals .
- SOLUTION: A tree in such that , and for every .
- COST FUNCTION: .
- OBJECTIVE: Minimize.
*Hardness:*APX-hard. [69]*Approx.:*Approximable within approximation ratio on metric instances, where is the the approximation ratio for the Steiner Tree Problem. [107]*Comment:*Approximable within approximation ratio on instances where edge weights are restricted to 1 and 2. [70]

2015-04-27 Revision: 288 PDF version