Given an undirected graph with nonnegative edge costs and an integer k, the
k-MST problem is that of finding a tree of minimum cost on k nodes. This p
roblem is known to be NP-hard. We present a simple approximation algorithm
that finds a solution whose cost is less than 17 times the cost of the opti
mum. This improves upon previous performance ratios for this problem - O(ro
ot k) due to Ravi et al., O(log(2) k) due to Awerbuch et al, and the previo
us best bound of O(log k) due to Rajagopalan and Vazirani. Given any 0 < a
< 1, we first present a bicriteria approximation algorithm that outputs a t
ree on p greater than or equal to ak vertices of total cost at most 2pL/(1-
a) k, where L is the cost of the optimal k-MST. The running time of the alg
orithm is O(n(2) log(2) n) on an n-node graph. We then show how to use this
algorithm to derive a constant factor approximation algorithm for the k-MS
T problem. The main subroutine in our algorithm is an approximation algorit
hm of Goemans and Williamson for the prize-collecting Steiner tree problem.
(C) 1999 Academic Press.