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 条
  • [21] Improved Approximation Algorithms for the Facility Location Problems with Linear/Submodular Penalties
    Li, Yu
    Du, Donglei
    Xiu, Naihua
    Xu, Dachuan
    ALGORITHMICA, 2015, 73 (02) : 460 - 482
  • [22] Improved approximation algorithm for universal facility location problem with linear penalties
    Xu, Yicheng
    Xu, Dachuan
    Du, Donglei
    Wu, Chenchen
    THEORETICAL COMPUTER SCIENCE, 2019, 774 (143-151) : 143 - 151
  • [23] Approximation algorithms for the stochastic priority facility location problem
    Li, Gaidi
    Wang, Zhen
    Wu, Chenchen
    OPTIMIZATION, 2013, 62 (07) : 919 - 928
  • [24] An Approximation Algorithm for the Dynamic Facility Location Problem with Submodular Penalties
    Chun-yan JIANG
    Gai-di LI
    Zhen WANG
    Acta Mathematicae Applicatae Sinica, 2014, (01) : 187 - 192
  • [25] An improved approximation algorithm for uncapacitated facility location problem with penalties
    Xu, Guang
    Xu, Jinhui
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2009, 17 (04) : 424 - 436
  • [26] An improved approximation algorithm for uncapacitated facility location problem with penalties
    Guang Xu
    Jinhui Xu
    Journal of Combinatorial Optimization, 2009, 17 : 424 - 436
  • [27] An improved approximation algorithm for uncapacitated facility location problem with penalties
    Xu, G
    Xu, JH
    COMPUTING AND COMBINATORICS, PROCEEDINGS, 2005, 3595 : 644 - 653
  • [28] An Approximation Algorithm for the Dynamic Facility Location Problem with Submodular Penalties
    Jiang, Chun-yan
    Li, Gai-di
    Wang, Zhen
    ACTA MATHEMATICAE APPLICATAE SINICA-ENGLISH SERIES, 2014, 30 (01): : 187 - 192
  • [29] An approximation algorithm for the dynamic facility location problem with submodular penalties
    Chun-yan Jiang
    Gai-di Li
    Zhen Wang
    Acta Mathematicae Applicatae Sinica, English Series, 2014, 30 : 187 - 192
  • [30] An approximation algorithm for the nth power metric facility location problem with linear penalties
    Wang, Yishui
    Xu, Dachuan
    Du, Donglei
    Wu, Chenchen
    OPTIMIZATION LETTERS, 2017, 11 (05) : 983 - 993
12345