A new approximation algorithm for the multilevel facility location problem

被引：29

作者：

Gabor, Adriana F. ^{[1
]}

van Ommeren, Jan-Kees C. W. ^{[2
]}

机构：

[1] Erasmus Univ, Inst Econometr, NL-3000 DR Rotterdam, Netherlands

[2] Univ Twente, Fac Elect Engn Math & Comp Sci, NL-7500 AE Enschede, Netherlands

来源：

DISCRETE APPLIED MATHEMATICS | 2010年 / 158卷 / 05期

关键词：

Facility location; Approximation algorithms; Randomized algorithms;

D O I：

10.1016/j.dam.2009.11.007

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

In this paper we propose a new integer programming formulation for the multilevel facility location problem and a novel 3-approximation algorithm based on LP-rounding. The linear program that we use has a polynomial number of variables and constraints, thus being more efficient than the one commonly used in the approximation algorithms for these types of problems. (C) 2009 Elsevier B.V. All rights reserved.

引用

页码：453 / 460

页数：8

共 21 条

[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] Improved approximation algorithms for multilevel facility location problems [J].

Ageev, AA .

OPERATIONS RESEARCH LETTERS, 2002, 30 (05) :327-332

[4]

[Anonymous], LECT NOTES COMPUTER

[5]

Arya V., 2001, P 33 ANN ACM S THEOR, P21

[6]

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

[7]

Byrka J, 2007, LECT NOTES COMPUT SC, V4627, P29

[8]

Charikar M., 1999, PROC 40 ANN IEEE S F, P378

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

Chudak, FA ;

Shmoys, DB .

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

[10]

Cornuejols G., 1990, Discrete Location Theory, P119

← 1 2 3 →