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 条
  • [31] An improved approximation algorithm for uncapacitated facility location problem with penalties
    Xu, Guang
    Xu, Jinhui
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2009, 17 (04) : 424 - 436
  • [32] An improved approximation algorithm for uncapacitated facility location problem with penalties
    Guang Xu
    Jinhui Xu
    Journal of Combinatorial Optimization, 2009, 17 : 424 - 436
  • [33] A Primal-Dual Approximation Algorithm for the Facility Location Problem with Submodular Penalties
    Donglei Du
    Ruixing Lu
    Dachuan Xu
    Algorithmica, 2012, 63 : 191 - 200
  • [34] An 0.828-approximation algorithm for the uncapacitated facility location problem
    Ageev, AA
    Sviridenko, MI
    DISCRETE APPLIED MATHEMATICS, 1999, 93 (2-3) : 149 - 156
  • [35] An improved approximation algorithm for uncapacitated facility location problem with penalties
    Xu, G
    Xu, JH
    COMPUTING AND COMBINATORICS, PROCEEDINGS, 2005, 3595 : 644 - 653
  • [36] An Approximation Algorithm for the Two-Stage Distributionally Robust Facility Location Problem
    Wu, Chenchen
    Du, Donglei
    Xu, Dachuan
    ADVANCES IN GLOBAL OPTIMIZATION, 2015, 95 : 99 - 107
  • [37] A new approximation algorithm for the k-facility location problem
    Zhang, Peng
    THEORETICAL COMPUTER SCIENCE, 2007, 384 (01) : 126 - 135
  • [38] Combinatorial approximation algorithms for the robust facility location problem with penalties
    Wang, Fengmin
    Xu, Dachuan
    Wu, Chenchen
    JOURNAL OF GLOBAL OPTIMIZATION, 2016, 64 (03) : 483 - 496
  • [39] A fast algorithm for facility location problem
    Shu, Wenhao
    Journal of Software, 2013, 8 (09) : 2360 - 2366
  • [40] Approximation algorithm for the k- product uncapacitated facility location problem
    Yi, Bin
    Li, Rongheng
    PROCEEDINGS OF 2010 3RD IEEE INTERNATIONAL CONFERENCE ON COMPUTER SCIENCE AND INFORMATION TECHNOLOGY (ICCSIT 2010), VOL 5, 2010, : 602 - 605
12345