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

• 成果类型: Article
• 署名作者: Arora, S; Karakostas, G
• 署名单位: Princeton University; McMaster University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-005-0693-1
• 发表日期: 2006
• 页码: 491-504
• 关键词: trees

摘要

For any epsilon > 0 we give a (2 + epsilon)-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 + epsilon)-approximation algorithm for the minimum tour that visits any k vertices, provided the edge costs satisfy the triangle inequality.