Allan Borodin, Jon Kleinberg, et al.
Journal of the ACM
Garg gives two approximation algorithms for the minimum-cost tree spanning k vertices in an undirected graph. Recently Jain and Vazirani discovered primal-dual approximation algorithms for the metric uncapacitated facility location and k-median problems. In this paper we show how Garg's algorithms can be explained simply with ideas introduced by Jain and Vazirani, in particular via a Lagrangean relaxation technique together with the primal-dual method for approximation algorithms. We also derive a constant factor approximation algorithm for the k-Steiner tree problem using these ideas, and point out the common features of these problems that allow them to be solved with similar techniques. © Springer-Verlag 2004.
Allan Borodin, Jon Kleinberg, et al.
Journal of the ACM
Aranyak Mehta, Tim Roughgarden, et al.
ACM Conference on Electronic Commerce 2007
Michel X. Goemans, David P. Williamson
SIAM Journal on Discrete Mathematics
Sanjeev Khanna, Madhu Sudan, et al.
SIAM Journal on Computing