- INSTANCE:
Graph
, the length function on each edge
, the rate function on each node
, source
, sets
of terminals with rate
- SOLUTION:
A tree
spanning all terminals.
- COST FUNCTION:
, where
.
- OBJECTIVE:
Minimize.
*Approx.:*Approximable within 3.802 [72]*Hardness:*NP-hard to within an approximation ratio 96/95 [36].*Comment:*Approximable within 1.960 for two non-zero rates.

2015-04-27 Revision: 288 PDF version