- INSTANCE:
A graph
, an edge cost function
, a probability distribution
over sets of source-sink pairs
, and an
parameter
.
- SOLUTION: A set of first-stage edges and for each , a set of second-stage edges such that (i) the edges in connect each of the pairs in D.
- COST FUNCTION: .
- OBJECTIVE: Minimize.
*Approx.:*Approximable within 5 [55][49].*Hardness:*NP hard.*Comment:*A basic building block is an -star consisting of a non-terminal , called the center, terminals and edges .

2015-04-27 Revision: 288 PDF version