A 2 + ɛ approximation algorithm for the k-MST problem

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