- INSTANCE:
Graph
,
length
for each
satisfying
the triangle inequality.
- SOLUTION:
A subset
such that .
- MEASURE:
Cost of the minimum spanning tree of the subgraph induced by
*V'*.

*Good News:*Approximable within 4 [225].*Bad News:*APX-complete and not approximable within 2 for any [225].*Comment:*Also called*Maximum Remote Minimum Spanning Tree*. Reduction from MAXIMUM INDEPENDENT SET. As hard to approximate as MAXIMUM INDEPENDENT SET for non-metric graphs. Approximable within 2.252 in the Euclidean metric, but not known to be NP-complete. MAXIMUM MINIMUM*K*-STEINER TREE is approximable within 3 and not approximable within 4/3, but approximable within 2.16 in the Euclidean metric. MAXIMUM MINIMUM METRIC*K*-TSP is approximable within 3 and not approximable within 2.