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 条
  • [1] A 2+ε approximation algorithm for the k-MST problem
    Arora, S
    Karakostas, G
    MATHEMATICAL PROGRAMMING, 2006, 107 (03) : 491 - 504
  • [2] Revisiting Garg's 2-Approximation Algorithm for the k-MST Problem in Graphs
    Breen, Emmett
    Mirka, Renee
    Wang, Zichen
    Williamson, David P.
    2023 SYMPOSIUM ON SIMPLICITY IN ALGORITHMS, SOSA, 2023, : 56 - 68
  • [3] An approximation algorithm for the Generalized k-Multicut problem
    Zhang, Peng
    Zhu, Daming
    Luan, Junfeng
    DISCRETE APPLIED MATHEMATICS, 2012, 160 (7-8) : 1240 - 1247
  • [4] An approximation algorithm to the k-Steiner Forest problem
    Zhang, Peng
    Xia, Mingji
    THEORETICAL COMPUTER SCIENCE, 2009, 410 (11) : 1093 - 1098
  • [5] Faster geometric k-point MST approximation
    Eppstein, D
    COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 1997, 8 (05): : 231 - 240
  • [6] An FPT approximation algorithm for the priority k-center problem
    Feng Q.
    Long R.
    Wu X.
    Zhong W.
    Zhongnan Daxue Xuebao (Ziran Kexue Ban)/Journal of Central South University (Science and Technology), 2023, 54 (07): : 2718 - 2724
  • [7] An approximation algorithm for the k-Level Concentrator Location Problem
    Drexl, Moritz A.
    OPERATIONS RESEARCH LETTERS, 2011, 39 (05) : 355 - 358
  • [8] An approximation algorithm for the uniform capacitated k-means problem
    Han, Lu
    Xu, Dachuan
    Du, Donglei
    Zhang, Dongmei
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2022, 44 (03) : 1812 - 1823
  • [9] APPROXIMATION ALGORITHM FOR SPHERICAL k-MEANS PROBLEM WITH PENALTY
    Wu, Chenchen
    Lv, Wei
    Wang, Yujie
    Xu, Dachuan
    JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION, 2022, 18 (04) : 2277 - 2287
  • [10] An approximation algorithm for the uniform capacitated k-means problem
    Lu Han
    Dachuan Xu
    Donglei Du
    Dongmei Zhang
    Journal of Combinatorial Optimization, 2022, 44 : 1812 - 1823
12345