A unified dual-fitting approximation algorithm for the facility location problems with linear/submodular penalties

被引：2
作者：
Li, Yu [1 ]
Du, Donglei [2 ]
Xiu, Naihua [1 ]
Xu, Dachuan [3 ]
机构：
[1] Beijing Jiaotong Univ, Sch Sci, Dept Math, Beijing 100044, Peoples R China
[2] Univ New Brunswick, Fac Business Adm, Fredericton, NB E3B 5A3, Canada
[3] Beijing Univ Technol, Dept Appl Math, Beijing 100124, Peoples R China
来源：
JOURNAL OF COMBINATORIAL OPTIMIZATION | 2014年 / 27卷 / 03期
基金：
加拿大自然科学与工程研究理事会;
关键词：
Approximation algorithm; Facility location problem; Linear programming; Submodular function;
D O I：
10.1007/s10878-012-9540-5
中图分类号：
TP39 [计算机的应用];
学科分类号：
081203 ; 0835 ;
摘要：
In this paper, we study two variants of the classical facility location problem, namely, the facility location problem with linear penalties (FLPLP) and the facility location problem with submodular penalties (FLPSP), respectively. We give a unified dual-fitting based approximation algorithm for these two problems, yielding approximation ratios 2 and 3 respectively.
引用
收藏
页码：609 / 620
页数：12
相关论文
共 50 条
  • [41] 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
  • [42] Approximation algorithms for the fault-tolerant facility location problem with penalties
    Ji, Sai
    Xu, Dachuan
    Du, Donglei
    Wu, Chenchen
    DISCRETE APPLIED MATHEMATICS, 2019, 264 : 62 - 75
  • [43] Approximation algorithms for the minimum power cover problem with submodular/linear penalties
    Liu, Xiaofei
    Li, Weidong
    Dai, Han
    THEORETICAL COMPUTER SCIENCE, 2022, 923 : 256 - 270
  • [44] An approximation algorithm for the group prize-collecting Steiner tree problem with submodular penalties
    Zhang, Jiaxuan
    Gao, Suogang
    Hou, Bo
    Liu, Wen
    COMPUTATIONAL & APPLIED MATHEMATICS, 2022, 41 (06)
  • [45] An approximation algorithm for the group prize-collecting Steiner tree problem with submodular penalties
    Jiaxuan Zhang
    Suogang Gao
    Bo Hou
    Wen Liu
    Computational and Applied Mathematics, 2022, 41
  • [46] Approximation algorithm for the parallel-machine scheduling problem with release dates and submodular rejection penalties
    Zheng, Hongye
    Gao, Suogang
    Liu, Wen
    Wu, Weili
    Du, Ding-Zhu
    Hou, Bo
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2022, 44 (01) : 343 - 353
  • [47] Approximation algorithm for the parallel-machine scheduling problem with release dates and submodular rejection penalties
    Hongye Zheng
    Suogang Gao
    Wen Liu
    Weili Wu
    Ding-Zhu Du
    Bo Hou
    Journal of Combinatorial Optimization, 2022, 44 : 343 - 353
  • [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 Algorithm for the Facility Location Problems
    An, Fengxian
    Wang, Zongyao
    Wang, Dongdong
    2010 2ND INTERNATIONAL ASIA CONFERENCE ON INFORMATICS IN CONTROL, AUTOMATION AND ROBOTICS (CAR 2010), VOL 1, 2010, : 56 - 59
  • [50] LOCAL SEARCH ALGORITHM FOR THE SQUARED METRIC k-FACILITY LOCATION PROBLEM WITH LINEAR PENALTIES
    Wang, Yishui
    Zhang, Dongmei
    Zhang, Peng
    Zhang, Yong
    JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION, 2021, 17 (04) : 2013 - 2030
12345