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 条

[21] A Local Search Approximation Algorithm for the k-means Problem with Penalties
Zhang, Dongmei
Hao, Chunlin
Wu, Chenchen
Xu, Dachuan
Zhang, Zhenning
COMPUTING AND COMBINATORICS, COCOON 2017, 2017, 10392 : 568 - 574
[22] An approximation algorithm for the k-prize-collecting multicut on a tree problem
Hou, Xin
Liu, Wen
Hou, Bo
THEORETICAL COMPUTER SCIENCE, 2020, 844 (844) : 26 - 33
[23] An approximation algorithm for the k-level capacitated facility location problem
Donglei Du
Xing Wang
Dachuan Xu
Journal of Combinatorial Optimization, 2010, 20 : 361 - 368
[24] Approximation algorithm for the k- product uncapacitated facility location problem
Yi, Bin
Li, Rongheng
PROCEEDINGS OF 2010 3RD IEEE INTERNATIONAL CONFERENCE ON COMPUTER SCIENCE AND INFORMATION TECHNOLOGY (ICCSIT 2010), VOL 5, 2010, : 602 - 605
[25] An approximation algorithm for soft capacitated k-facility location problem
Jiang, Yanjun
Xu, Dachuan
Du, Donglei
Wu, Chenchen
Zhang, Dongmei
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2018, 35 (02) : 493 - 511
[26] An approximation algorithm for the k-level stochastic facility location problem
Wang, Zhen
Du, Donglei
Gabor, Adriana F.
Xu, Dachuan
OPERATIONS RESEARCH LETTERS, 2010, 38 (05) : 386 - 389
[27] An approximation algorithm for the k-level facility location problem with outliers
Lu Han
Dachuan Xu
Dandan Liu
Chenchen Wu
Optimization Letters, 2021, 15 : 2053 - 2065
[28] An approximation algorithm for soft capacitated k-facility location problem
Yanjun Jiang
Dachuan Xu
Donglei Du
Chenchen Wu
Dongmei Zhang
Journal of Combinatorial Optimization, 2018, 35 : 493 - 511
[29] An approximation algorithm for the k-level facility location problem with outliers
Han, Lu
Xu, Dachuan
Liu, Dandan
Wu, Chenchen
OPTIMIZATION LETTERS, 2021, 15 (06) : 2053 - 2065
[30] An approximation algorithm for the k-level capacitated facility location problem
Du, Donglei
Wang, Xing
Xu, Dachuan
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2010, 20 (04) : 361 - 368

← 1 2 3 4 5 →