A constant-factor approximation algorithm for the k MST problem (extended abstract)
Avrim L. Blum, R. Ravi, Santosh Vempala · 1996
Given an undirected graph with non-negative edge costs and an integer k, the k-MST problem is that of finding a tree of minimum cost on k nodes.This problem 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 optimum.This improves upon previous performance ratios for this problem -O(w) due to Ravi et al., 0(log2 k) due to Awerbuch et al, and the previous best bound of O(log k) due to Rajagopalan and Vazirani.Given any O < cr < 1, we first present a bicriteria approximation algorithm that ~o~tputs a tree on p z cYk vertices of total cost at most ~1~, where L is the cost of the optimal k-