摘要: We present a polynomial time 2-approximation algorithm for the problem of finding minimum tree that spans at least k vertices. Our result also leads to tour visits vertices and 3-approximation maximum number can be spanned by length most given bound.
acm.org
sci-hub.se 参考文章(16)
Joseph S. B. Mitchell, Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k -MST, and Related Problems SIAM Journal on Computing. ,vol. 28, pp. 1298- 1309 ,(1999) , 10.1137/S0097539796309764
David Eppstein, Faster geometric k -point MST approximation Computational Geometry: Theory and Applications. ,vol. 8, pp. 231- 240 ,(1997) , 10.1016/S0925-7721(96)00021-1
Sunil Arya, H. Ramesh, A 2.5-factor approximation algorithm for the k -MST problem Information Processing Letters. ,vol. 65, pp. 117- 118 ,(1998) , 10.1016/S0020-0190(98)00010-6
Joseph S. B. Mitchell, Avrim Blum, Prasad Chalasani, Santosh Vempala, A Constant-Factor Approximation Algorithm for the Geometric k -MST Problem in the Plane SIAM Journal on Computing. ,vol. 28, pp. 771- 781 ,(1999) , 10.1137/S0097539796303299
D. J. Rosenkrantz, R. Sundaram, S. S. Ravi, M. V. Marathe, R. Ravi, Spanning trees short or small symposium on discrete algorithms. pp. 546- 555 ,(1994) , 10.5555/314464.314644
Naveen Garg, Dorit S. Hochbaum, An O(log k) approximation algorithm for the k minimum spanning tree problem in the plane Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94. pp. 432- 438 ,(1994) , 10.1145/195058.195218
Avrim Blum, Prasad Chalasani, Santosh Vempala, A constant-factor approximation for the k-MST problem in the plane symposium on the theory of computing. pp. 294- 302 ,(1995) , 10.1145/225058.225143
Maria Minko, David R Karger, The prize collecting Steiner tree problem: theory and practice symposium on discrete algorithms. pp. 760- 769 ,(2000) , 10.5555/338219.338637
Avrim Blum, R. Ravi, Santosh Vempala, A constant-factor approximation algorithm for the k MST problem (extended abstract) symposium on the theory of computing. pp. 442- 448 ,(1996) , 10.1145/237814.237992
Baruch Awerbuch, Yossi Azar, Avrim Blum, Santosh Vempala, Improved approximation guarantees for minimum-weight k-trees and prize-collecting salesmen symposium on the theory of computing. pp. 277- 283 ,(1995) , 10.1145/225058.225139