- INSTANCE: Graph , edge costs , set of terminals , a penalty function .
- SOLUTION: Tree in such that , .
- COST FUNCTION:
- OBJECTIVE: Minimize.
*Approx.:*Can be solved exactly in polynomial time [63].*Comment:*This entry covers the penalty-based variant of the Prize-Collecting Steiner Tree Problem. The quota-based Prize-Collecting Steiner Tree Problem, as well as the related Steiner Forest problems can also be solved in polynomial time [63].

2015-04-27 Revision: 288 PDF version