Next:
Quota Steiner Tree Problem
Up:
Steiner Tree Problems
Previous:
Fractional Steiner Tree Problem
Budget Steiner Tree Problem with Profits
I
NSTANCE:
Graph
, a cost function
, a revenue function
, budget
.
S
OLUTION:
A tree
in
such that
,
and
.
C
OST FUNCTION:
O
BJECTIVE:
Maximize.
Approx.:
Approximable within
for every
[
83
]
Hardness:
NP-hard.
2015-04-27 Revision: 288
PDF version