An approximation algorithm for the dynamic facility location problem with outliers

被引：2

作者：

Jiang, Yanjun ^{[1
]}

Xu, Dachuan ^{[1
]}

Du, Donglei ^{[2
]}

Zhang, Dongmei ^{[3
]}

机构：

[1] Beijing Univ Technol, Coll Appl Sci, Dept Informat & Operat Res, 100 Pingleyuan, Beijing 100124, Peoples R China

[2] Univ New Brunswick, Fac Business Adm, Fredericton, NB E3B 5A3, Canada

[3] Shandong Jianzhu Univ, Sch Comp Sci & Technol, Jinan 250101, Shandong, Peoples R China

来源：

OPTIMIZATION LETTERS | 2019年 / 13卷 / 03期

基金：

加拿大自然科学与工程研究理事会;

关键词：

Approximation algorithm; Facility location problem; Primal-dual; Approximation ratio;

D O I：

10.1007/s11590-017-1153-6

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

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

页数：11

共 24 条

[1] Approximation algorithms for hard capacitated k-facility location problems [J].

Aardal, Karen ;

van den Berg, Pieter L. ;

Gijswijt, Dion ;

Li, Shanfei .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2015, 242 (02) :358-368

[2] Improved combinatorial approximation algorithms for the k-level facility location problem [J].

Ageev, A ;

Ye, YY ;

Zhang, JW .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2004, 18 (01) :207-217

[3]

[Anonymous], 1998, COMMUNICATION

[4]

Byrka J., 2016, P 18 C INT PROGR COM

[5] Improved combinatorial algorithms for facility location problems [J].

Charikar, M ;

Guha, S .

SIAM JOURNAL ON COMPUTING, 2005, 34 (04) :803-824

[6]

Charikar M, 2001, SIAM PROC S, P642

[7] Approximation Algorithms for Soft-Capacitated Facility Location in Capacitated Network Design [J].

Chen, Xujin ;

Chen, Bo .

ALGORITHMICA, 2009, 53 (03) :263-297

[8] Improved approximation algorithms for the uncapacitated facility location problem [J].

Chudak, FA ;

Shmoys, DB .

SIAM JOURNAL ON COMPUTING, 2003, 33 (01) :1-25

[9] A Primal-Dual Approximation Algorithm for the Facility Location Problem with Submodular Penalties [J].

Du, Donglei ;

Lu, Ruixing ;

Xu, Dachuan .

ALGORITHMICA, 2012, 63 (1-2) :191-200

[10] Greedy strikes back: Improved facility location algorithms [J].

Guha, S ;

Khuller, S .

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 1999, 31 (01) :228-248

← 1 2 3 →