- INSTANCE: Metric space , set of sinks , edge costs , bound .
- SOLUTION: A stretched tree consisting of an arborescence , a mapping such that is a one-to-one mapping between the leaves of and and a cost function such that for every edge of , and furthermore, for each pair of root-to-leaf paths in ,
- COST FUNCTION:
- OBJECTIVE: Minimize.
*Approx.:*Approximable within approximation ratio 14 when the root is not fixed as a part of the instance [110]. Approximable within when the root is given as part of the input [28].*Hardness:*NP-hard [28]. Also NP-hard in the two-dimensional rectilinear case [110].

2015-04-27 Revision: 288 PDF version