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 [10]. As in [10] 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.
Keywords k-Minimum Spanning Tree - Approximation algorithm - Primal-Dual schema
Research supported by NSF CAREER award NSF CCR-9502747, NSF grants CCR-0205594 and CCR-0098180, an Alfred Sloan Fellowship,
and a Packard Fellowship.
Research supported by an NSERC Discovery grant.