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 [J].

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 [J].

Hou, Xin ;

Liu, Wen ;

Hou, Bo .

THEORETICAL COMPUTER SCIENCE, 2020, 844 (844) :26-33

[23] Approximation algorithm for the k- product uncapacitated facility location problem [J].

Yi, Bin ;

Li, Rongheng .

PROCEEDINGS OF 2010 3RD IEEE INTERNATIONAL CONFERENCE ON COMPUTER SCIENCE AND INFORMATION TECHNOLOGY (ICCSIT 2010), VOL 5, 2010, :602-605

[24] An approximation algorithm for the k-level capacitated facility location problem [J].

Donglei Du ;

Xing Wang ;

Dachuan Xu .

Journal of Combinatorial Optimization, 2010, 20 :361-368

[25] An approximation algorithm for the k-level stochastic facility location problem [J].

Wang, Zhen ;

Du, Donglei ;

Gabor, Adriana F. ;

Xu, Dachuan .

OPERATIONS RESEARCH LETTERS, 2010, 38 (05) :386-389

[26] An approximation algorithm for soft capacitated k-facility location problem [J].

Jiang, Yanjun ;

Xu, Dachuan ;

Du, Donglei ;

Wu, Chenchen ;

Zhang, Dongmei .

JOURNAL OF COMBINATORIAL OPTIMIZATION, 2018, 35 (02) :493-511

[27] An approximation algorithm for the k-level facility location problem with outliers [J].

Lu Han ;

Dachuan Xu ;

Dandan Liu ;

Chenchen Wu .

Optimization Letters, 2021, 15 :2053-2065

[28] An approximation algorithm for the k-level facility location problem with outliers [J].

Han, Lu ;

Xu, Dachuan ;

Liu, Dandan ;

Wu, Chenchen .

OPTIMIZATION LETTERS, 2021, 15 (06) :2053-2065

[29] An approximation algorithm for soft capacitated k-facility location problem [J].

Yanjun Jiang ;

Dachuan Xu ;

Donglei Du ;

Chenchen Wu ;

Dongmei Zhang .

Journal of Combinatorial Optimization, 2018, 35 :493-511

[30] An approximation algorithm for the k-level capacitated facility location problem [J].

Du, Donglei ;

Wang, Xing ;

Xu, Dachuan .

JOURNAL OF COMBINATORIAL OPTIMIZATION, 2010, 20 (04) :361-368

← 1 2 3 4 5 →