- INSTANCE:
Graph
, set of terminal pairs
,
cost function
, penalty function
.
- SOLUTION: A pair , where is a forest and contains all the terminal pairs that are not connected by
- COST FUNCTION:
.
- OBJECTIVE: Minimize.
*Approx.:*Approximable within approximation ratio using a primal-dual approach. Approximable within approximation ratio by an LP-Rounding algorithm [100],[57].*Hardness:*NP-hard to approximate within 96/95 [36].*Comment:*PTAS exists for the special case when G is planar graph [29].

2015-04-27 Revision: 288 PDF version