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 条
[41]   Approximation algorithm for the multicovering problem [J].
Gorgi, Abbass ;
El Ouali, Mourad ;
Srivastav, Anand ;
Hachimi, Mohamed .
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2021, 41 (02) :433-450
[42]   An approximation algorithm for the spherical k-means problem with outliers by local search [J].
Yishui Wang ;
Chenchen Wu ;
Dongmei Zhang ;
Juan Zou .
Journal of Combinatorial Optimization, 2022, 44 :2410-2422
[43]   Approximation Algorithm for the k-Product Uncapacitated Facility Location Problem with Penalties [J].
Yang, Pei-Jia ;
Luo, Wen-Chang .
JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF CHINA, 2025, 13 (01) :287-296
[44]   A 2-Approximation Algorithm for the Graph 2-Clustering Problem [J].
Il'ev, Victor ;
Il'eva, Svetlana ;
Morshinin, Alexander .
MATHEMATICAL OPTIMIZATION THEORY AND OPERATIONS RESEARCH, 2019, 11548 :295-308
[45]   A Deterministic Algorithm for the MST Problem in Constant Rounds of Congested Clique [J].
Nowicki, Krzysztof .
STOC '21: PROCEEDINGS OF THE 53RD ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING, 2021, :1154-1165
[46]   Approximation Algorithm for the Balanced 2-Correlation Clustering Problem [J].
Ji, Sai ;
Xu, Dachuan ;
Du, Donglei ;
Gai, Ling ;
Zhao, Zhongrui .
TSINGHUA SCIENCE AND TECHNOLOGY, 2022, 27 (05) :777-784
[47]   A Local 2-Approximation Algorithm for the Vertex Cover Problem [J].
Astrand, Matti ;
Floreen, Patrik ;
Polishchuk, Valentin ;
Rybicki, Joel ;
Suomela, Jukka ;
Uitto, Jara .
DISTRIBUTED COMPUTING, PROCEEDINGS, 2009, 5805 :191-205
[48]   An approximation algorithm for the k-median warehouse-retailer network design problem [J].
Yu Li ;
NaiHua Xiu ;
DaChuan Xu .
Science China Mathematics, 2013, 56 :2381-2388
[49]   AN IMPROVED APPROXIMATION ALGORITHM FOR THE k-PRIZE-COLLECTING MINIMUM POWER COVER PROBLEM [J].
Wang, Wencheng ;
Cheng, Binhui ;
Li, Jianglin ;
Chen, Yinhua ;
Zhang, Tongquan .
JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION, 2024, 20 (04) :1703-1718
[50]   A 3-approximation algorithm for the k-level uncapacitated facility location problem [J].
Aardal, K ;
Chudak, FA ;
Shmoys, DB .
INFORMATION PROCESSING LETTERS, 1999, 72 (5-6) :161-167
12345