, a metric given by edge weights
and a subset
of required vertices.
the problem
is approximable within
[
157
].
The variation in which the diameter of the tree is bounded by a
constant
d
the problem is not approximable within
for any
, unless NP
,
but approximable within
for
[
35
]
and within
for any constant
[
244
].
A prize-collecting variation in which a penalty is associated with each vertex
and the goal is to minimize the cost of the tree and the vertices in
S
not in
the tree is approximable within
2-1/(|V|-1)
[
134
].
Another prize-collecting variation in which a salesperson has to sell some
quota
R
while traveling the least distance possible is approximable within
[
29
].
The variation in which an integer
is given in input and at least
k
vertices of
S
must be included in the subtree is approximable within
[
309
].
Variation in which there are groups of required vertices and each group
must be touched by the Steiner tree is approximable within
g-1
, where
g
is the number of groups [
185
]; when the number of groups
is unbounded the problem is harder than M
INIMUM
D
OMINATING
S
ET
to approximate,
even if all edge weights are 1 [
186
].
The constrained variation in which the input is extended with a positive
integer
k
and a subset
T
of
E
, and the problem is to find the
Steiner tree of weight at most
k
that contains the largest number of
edges from
T
, is not approximable within
for some
[
352
].
If the solution is allowed to be a forest with at most
q
trees, for a
given constant
q
, the problem is approximable within
2(1-1/(|S|-q+1))
[
306
].
Finally, if the topology of the Steiner tree is given as input, the
problem admits a PTAS [
190
].
Viggo Kann