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 条
  • [21] An approximation algorithm for the submodular multicut problem in trees with linear penalties
    Chenfei Hou
    Suogang Gao
    Wen Liu
    Weili Wu
    Ding-Zhu Du
    Bo Hou
    Optimization Letters, 2021, 15 : 1105 - 1112
  • [22] 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
  • [23] An approximation algorithm for submodular hitting set problem with linear penalties
    Du, Shaojing
    Gao, Suogang
    Hou, Bo
    Liu, Wen
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2020, 40 (04) : 1065 - 1074
  • [24] An approximation algorithm for submodular hitting set problem with linear penalties
    Shaojing Du
    Suogang Gao
    Bo Hou
    Wen Liu
    Journal of Combinatorial Optimization, 2020, 40 : 1065 - 1074
  • [25] An approximation algorithm for the submodular multicut problem in trees with linear penalties
    Hou, Chenfei
    Gao, Suogang
    Liu, Wen
    Wu, Weili
    Du, Ding-Zhu
    Hou, Bo
    OPTIMIZATION LETTERS, 2021, 15 (04) : 1105 - 1112
  • [26] A Primal Dual Approximation Algorithm for the Multicut Problem in Trees with Submodular Penalties
    Liu, Xiaofei
    Li, Weidong
    ALGORITHMIC ASPECTS IN INFORMATION AND MANAGEMENT, AAIM 2019, 2019, 11640 : 203 - 211
  • [27] An improved approximation algorithm for uncapacitated facility location problem with penalties
    Xu, Guang
    Xu, Jinhui
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2009, 17 (04) : 424 - 436
  • [28] An improved approximation algorithm for uncapacitated facility location problem with penalties
    Guang Xu
    Jinhui Xu
    Journal of Combinatorial Optimization, 2009, 17 : 424 - 436
  • [29] An improved approximation algorithm for uncapacitated facility location problem with penalties
    Xu, G
    Xu, JH
    COMPUTING AND COMBINATORICS, PROCEEDINGS, 2005, 3595 : 644 - 653
  • [30] Approximation Algorithms for the Robust Facility Location Problem with Penalties
    Wang, Fengmin
    Xu, Dachuan
    Wu, Chenchen
    ADVANCES IN GLOBAL OPTIMIZATION, 2015, 95 : 129 - 135
12345