An approximation algorithm for the dynamic facility location problem with outliers

被引：0
|
作者：
Yanjun Jiang
Dachuan Xu
Donglei Du
Dongmei Zhang
机构：
[1] Beijing University of Technology,Department of Information and Operations Research, College of Applied Sciences
[2] University of New Brunswick,Faculty of Business Administration
[3] Shandong Jianzhu University,School of Computer Science and Technology
来源：
Optimization Letters | 2019年 / 13卷
关键词：
Approximation algorithm; Facility location problem; Primal-dual; Approximation ratio;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
In this article, we investigate the dynamic (multi-period) facility location problem with potentially unserved clients or outliers. We propose a 3-approximation primal-dual algorithm based on an integer linear program formulation of the problem. We further improve the approximation ratio to 2 by combining the cost scaling and greedy improvement techniques.
引用
收藏
页码：561 / 571
页数：10
相关论文
共 50 条
  • [21] Approximation Algorithms for the Robust Facility Location Problem with Penalties
    Wang, Fengmin
    Xu, Dachuan
    Wu, Chenchen
    ADVANCES IN GLOBAL OPTIMIZATION, 2015, 95 : 129 - 135
  • [22] Approximation Algorithms for the Priority Facility Location Problem with Penalties
    Wang Fengmin
    Xu Dachuan
    Wu Chenchen
    JOURNAL OF SYSTEMS SCIENCE & COMPLEXITY, 2015, 28 (05) : 1102 - 1114
  • [23] Approximation algorithms for the priority facility location problem with penalties
    Fengmin Wang
    Dachuan Xu
    Chenchen Wu
    Journal of Systems Science and Complexity, 2015, 28 : 1102 - 1114
  • [24] Approximation Algorithms for the Priority Facility Location Problem with Penalties
    WANG Fengmin
    XU Dachuan
    WU Chenchen
    JournalofSystemsScience&Complexity, 2015, 28 (05) : 1102 - 1114
  • [25] An approximation algorithm for a competitive facility location problem with network effects
    Kung, Ling-Chieh
    Liao, Wei-Hung
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2018, 267 (01) : 176 - 186
  • [26] 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
  • [27] 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
  • [28] 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
  • [29] 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
  • [30] 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
12345