ND5 M AXIMUM M INIMUM M ETRIC K -S PANNING T REE

     
• I NSTANCE : Graph , length for each satisfying the triangle inequality.
• S OLUTION : A subset such that |V'|=k .
• M EASURE : Cost of the minimum spanning tree of the subgraph induced by V' .

• Good News: Approximable within 4 [ 154 ].
• Bad News: A PX -complete and not approximable within 2 for any [ 154 ].
• Comment: Also called Maximum Remote Minimum Spanning Tree .     Reduction from M AXIMUM I NDEPENDENT S ET . As hard to approximate as M AXIMUM I NDEPENDENT S ET for non-metric graphs. Approximable within 2.252 in the Euclidean metric, but not known to be NP-complete.   The Maximum Minimum k -Steiner Tree problem 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 .