An Approximation Algorithm for the Dynamic k-level Facility Location Problem

被引：0

作者：

Wang, Limin ^{[1
]}

Zhang, Zhao ^{[2
]}

Xu, Dachuan ^{[3
]}

Zhang, Xiaoyan ^{[4
,5
]}

机构：

[1] Nanjing Univ, State Key Lab Novel Software Technol, Nanjing 210023, Jiangsu, Peoples R China

[2] Zhejiang Normal Univ, Coll Math & Comp Sci, Jinhua 321004, Zhejiang, Peoples R China

[3] Beijing Univ Technol, Beijing Inst Sci & Engn Comp, Beijing 100124, Peoples R China

[4] Nanjing Normal Univ, Sch Math Sci, Nanjing 210023, Peoples R China

[5] Nanjing Normal Univ, Inst Math, Nanjing 210023, Peoples R China

来源：

ALGORITHMIC ASPECTS IN INFORMATION AND MANAGEMENT, AAIM 2019 | 2019年 / 11640卷

基金：

中国国家自然科学基金;

关键词：

Approximation algorithm; Primal-dual; Dynamic; Facility location;

D O I：

10.1007/978-3-030-27195-4_26

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

In this paper, we consider the dynamic k-level facility location problem, which is a generalization of the uncapacitated k-level facility location problem when considering time factor. We present a combinatorial primal-dual approximation algorithm for the problem which finds a solution within 6 times the optimum. This approximation ratio under a dynamic setting coincides with that of the simple dual ascent 6-approximation algorithm for the (static) multilevel facility location problem (Bumb, 2001) with a weak triangle inequality property.

引用

页码：284 / 291

页数：8

共 13 条

[1] A 3-approximation algorithm for the k-level uncapacitated facility location problem [J].

Aardal, K ;

Chudak, FA ;

Shmoys, DB .

INFORMATION PROCESSING LETTERS, 1999, 72 (5-6) :161-167

[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]

Bumb A, 2001, LECT NOTES COMPUT SC, V2129, P55

[4]

Chen B., 2010, LNCS, P253, DOI [10.1007/978-3-642-14355-7_26, DOI 10.1007/978-3-642-14355-7_26]

[5]

Cornunejols G., 1990, Discrete Location Theory, P119

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

Guha, S ;

Khuller, S .

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

[7] Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation [J].

Jain, K ;

Vazirani, VV .

JOURNAL OF THE ACM, 2001, 48 (02) :274-296

[8]

Mahdian M, 2002, LECT NOTES COMPUT SC, V2462, P229

[9] Cost-Distance: Two metric network design [J].

Meyerson, A ;

Munagala, K ;

Plotkin, S .

41ST ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 2000, :624-630

[10]

Shmoys D.B., 1997, APPROXIMATION ALGORI, V1997

← 1 2 →