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

被引：0

作者：

Sanjeev Arora

George Karakostas

机构：

[1] Princeton University,Department of Computer Science

[2] McMaster University,Department of Computing & Software

来源：

Mathematical Programming | 2006年 / 107卷

关键词：

-Minimum Spanning Tree; Approximation algorithm; Primal-Dual schema;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

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

引用

页码：491 / 504

页数：13

共 50 条

[31] An Approximation Algorithm for the Dynamic k-level Facility Location Problem [J].

Wang, Limin ;

Zhang, Zhao ;

Xu, Dachuan ;

Zhang, Xiaoyan .

ALGORITHMIC ASPECTS IN INFORMATION AND MANAGEMENT, AAIM 2019, 2019, 11640 :284-291

[32] A 2-approximation algorithm for the network substitution problem [J].

Pisaruk, NN .

OPERATIONS RESEARCH LETTERS, 2006, 34 (01) :94-96

[33] An Approximation Algorithm for the k-Connected Location Set Cover Problem with Color-Spanning Constraint [J].

Wang, Yin ;

Xu, Yinfeng .

ADVANCES IN PRODUCTION MANAGEMENT SYSTEMS: ARTIFICIAL INTELLIGENCE FOR SUSTAINABLE AND RESILIENT PRODUCTION SYSTEMS (APMS 2021), PT III, 2021, 632 :317-325

[34] Approximation Algorithm for the Minimum Connected k-Path Vertex Cover Problem [J].