Next: MINIMUM DIAMETER SPANNING SUBGRAPH Up: Spanning Trees Previous: MAXIMUM LEAF SPANNING TREE Index

### MAXIMUM MINIMUM METRIC K-SPANNING TREE

- INSTANCE: Graph , length for each satisfying the triangle inequality.

- SOLUTION: A subset such that |V'|=k.

- MEASURE: Cost of the minimum spanning tree of the subgraph induced by V'.

- Good News: Approximable within 4 [212].

- Bad News: APX-complete and not approximable within 2 for any [212].

- 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.