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 条
  • [41] An approximation algorithm for the k-level capacitated facility location problem
    Donglei Du
    Xing Wang
    Dachuan Xu
    Journal of Combinatorial Optimization, 2010, 20 : 361 - 368
  • [42] An approximation algorithm for the k-level stochastic facility location problem
    Wang, Zhen
    Du, Donglei
    Gabor, Adriana F.
    Xu, Dachuan
    OPERATIONS RESEARCH LETTERS, 2010, 38 (05) : 386 - 389
  • [43] An approximation algorithm for soft capacitated k-facility location problem
    Jiang, Yanjun
    Xu, Dachuan
    Du, Donglei
    Wu, Chenchen
    Zhang, Dongmei
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2018, 35 (02) : 493 - 511
  • [44] A Local Search Approximation Algorithm for the Restricted Universal Facility Location Problem
    Kanodia, Uttam
    Shukla, K. K.
    PROCEEDINGS OF THE 2016 INTERNATIONAL CONFERENCE ON DATA SCIENCE & ENGINEERING (ICDSE), 2016, : 151 - 153
  • [45] 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
  • [46] An approximation algorithm for the k-level capacitated facility location problem
    Du, Donglei
    Wang, Xing
    Xu, Dachuan
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2010, 20 (04) : 361 - 368
  • [47] Approximation algorithms for the stochastic priority facility location problem
    Li, Gaidi
    Wang, Zhen
    Wu, Chenchen
    OPTIMIZATION, 2013, 62 (07) : 919 - 928
  • [48] An incremental algorithm for the uncapacitated facility location problem
    Arulselvan, Ashwin
    Maurer, Olaf
    Skutella, Martin
    NETWORKS, 2015, 65 (04) : 306 - 311
  • [49] A primal-dual approximation algorithm for stochastic facility location problem with service installation costs
    Wang, Xing
    Xu, Dachuan
    Zhao, Xinyuan
    FRONTIERS OF MATHEMATICS IN CHINA, 2011, 6 (05) : 957 - 964
  • [50] A primal-dual approximation algorithm for stochastic facility location problem with service installation costs
    Xing Wang
    Dachuan Xu
    Xinyuan Zhao
    Frontiers of Mathematics in China, 2011, 6 : 957 - 964
12345