Next: Zero Skew Tree Problem
Up: Steiner Tree Problems
Previous: Polymatroid Directed Steiner Problem
, sets of terminals
with node rates
and edge lengths
- COST FUNCTION:
Approximable within 1.960 for the case of two non-zero rates. Approximable within 3.802 for the case of unbounded number of rates . For the case of three non-zero rates, the problem admits an 1.522 approximation algorithm 
NP-hard to approximate within 96/95 .
are the distinct rates.
denotes the set of all nodes with rate
The cost of an edge in the solution tree
(rate of edge
)is the maximum rate in the component
2015-04-27 Revision: 288 PDF version