For any ε > 0 we give a (2 + ε)-approximation algorithm for the problem of finding a minimum tree spanning any k vertices in a graph (k-MST), improving a 3-approximation algorithm by Garg . As in  the algorithm extends to a (2 + ε)-approximation algorithm for the minimum tour that visits any k vertices, provided the edge costs satisfy the triangle inequality.
All Science Journal Classification (ASJC) codes
- Approximation algorithm
- Primal-Dual schema
- k-Minimum Spanning Tree