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 条
  • [31] A combinatorial 2.375-approximation algorithm for the facility location problem with submodular penalties
    Li, Yu
    Du, Donglei
    Xiu, Naihua
    Xu, Dachuan
    THEORETICAL COMPUTER SCIENCE, 2013, 476 : 109 - 117
  • [32] An approximation algorithm for the nth power metric facility location problem with linear penalties
    Yishui Wang
    Dachuan Xu
    Donglei Du
    Chenchen Wu
    Optimization Letters, 2017, 11 : 983 - 993
  • [33] A Primal-Dual Approximation Algorithm for the Facility Location Problem with Submodular Penalties
    Du, Donglei
    Lu, Ruixing
    Xu, Dachuan
    ALGORITHMICA, 2012, 63 (1-2) : 191 - 200
  • [34] A (5.83+ε)-Approximation Algorithm for Universal Facility Location Problem with Linear Penalties
    Xu, Yicheng
    Xu, Dachuan
    Du, Donglei
    Wu, Chenchen
    COMBINATORIAL OPTIMIZATION AND APPLICATIONS, (COCOA 2015), 2015, 9486 : 72 - 81
  • [35] A Primal-Dual Approximation Algorithm for the Facility Location Problem with Submodular Penalties
    Donglei Du
    Ruixing Lu
    Dachuan Xu
    Algorithmica, 2012, 63 : 191 - 200
  • [36] Approximation Algorithm for the k-Product Uncapacitated Facility Location Problem with Penalties
    Yang, Pei-Jia
    Luo, Wen-Chang
    JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF CHINA, 2025, 13 (01) : 287 - 296
  • [37] Approximation Algorithms for a Facility Location Problem with Service Capacities
    Massberg, Jens
    Vygen, Jens
    ACM TRANSACTIONS ON ALGORITHMS, 2008, 4 (04)
  • [38] A 3-Approximation Algorithm for Uniform Capacitated Facility Location Problem with Penalties
    Bansal, Manisha
    Aggarwal, Seema
    Aggarwal, Geeta
    Gupta, Neelima
    JOURNAL OF ELECTRICAL SYSTEMS, 2024, 20 (07) : 461 - 468
  • [39] AN APPROXIMATION ALGORITHM FOR THE k-LEVEL FACILITY LOCATION PROBLEM WITH SUBMODULAR PENALTIES
    Li, Gaidi
    Wang, Zhen
    Xu, Dachuan
    JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION, 2012, 8 (03) : 521 - 529
  • [40] 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
12345