Approximation algorithms for the fault-tolerant facility location problem with penalties

被引：1
作者：
Ji, Sai [1 ]
Xu, Dachuan [1 ]
Du, Donglei [2 ]
Wu, Chenchen [3 ]
机构：
[1] Beijing Univ Technol, Coll Appl Math, Dept Informat & Operat Res, Beijing, Peoples R China
[2] Univ New Brunswick, Fac Business Adm, Fredericton, NB, Canada
[3] Tianjin Univ Technol, Coll Sci, Tianjin, Peoples R China
来源：
DISCRETE APPLIED MATHEMATICS | 2019年 / 264卷
基金：
中国国家自然科学基金;
关键词：
Approximation algorithm; Fault-tolerant; Facility location problem; Penalty;
D O I：
10.1016/j.dam.2019.01.003
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
We study the fault-tolerant facility location problem with penalties (FTFLPWP). We present an LP-rounding 4-approximation algorithm. Then we apply the randomized rounding technique to improve the approximation to 3.16, which is further improved to 2.408 by the greedy augmentation technique. (C) 2019 Elsevier B.V. All rights reserved.
引用
收藏
页码：62 / 75
页数：14
相关论文
共 50 条
  • [41] Improved Approximation Algorithms for Capacitated Fault-Tolerant k-Center
    Cristina G. Fernandes
    Samuel P. de Paula
    Lehilton L. C. Pedrosa
    Algorithmica, 2018, 80 : 1041 - 1072
  • [42] The Reliable Facility Location Problem: Formulations, Heuristics, and Approximation Algorithms
    Shen, Zuo-Jun Max
    Zhan, Roger Lezhou
    Zhang, Jiawei
    INFORMS JOURNAL ON COMPUTING, 2011, 23 (03) : 470 - 482
  • [43] Approximation and Heuristic Algorithms for the Priority Facility Location Problem with Outliers
    Luo, Hang
    Han, Lu
    Shuai, Tianping
    Wang, Fengmin
    TSINGHUA SCIENCE AND TECHNOLOGY, 2024, 29 (06): : 1694 - 1702
  • [44] Approximation algorithms for the partition set cover problem with penalties
    Qi Wang
    Bo Hou
    Gengsheng Zhang
    Yisheng Zhou
    Wen Liu
    Journal of Combinatorial Optimization, 2025, 49 (5)
  • [45] Algorithms for connected set cover problem and fault-tolerant connected set cover problem
    Zhang, Zhao
    Gao, Xiaofeng
    Wu, Weili
    THEORETICAL COMPUTER SCIENCE, 2009, 410 (8-10) : 812 - 817
  • [46] A note on LP-based approximation algorithms for capacitated facility location problem
    Miao, Runjie
    Yuan, Jinjiang
    THEORETICAL COMPUTER SCIENCE, 2022, 932 : 31 - 40
  • [47] Improved combinatorial approximation algorithms for the k-level facility location problem
    Ageev, A
    Ye, YY
    Zhang, JW
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2004, 18 (01) : 207 - 217
  • [48] An Approximation Algorithm for the Risk-Adjusted Two-Stage Stochastic Facility Location Problem with Penalties
    Shao J.
    Xu D.
    Journal of the Operations Research Society of China, 2013, 1 (3) : 339 - 346
  • [49] An approximation algorithm for k-facility location problem with linear penalties using local search scheme
    Wang, Yishui
    Xu, Dachuan
    Du, Donglei
    Wu, Chenchen
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2018, 36 (01) : 264 - 279
  • [50] An approximation algorithm for k-facility location problem with linear penalties using local search scheme
    Yishui Wang
    Dachuan Xu
    Donglei Du
    Chenchen Wu
    Journal of Combinatorial Optimization, 2018, 36 : 264 - 279
12345