Approximation algorithm for facility location with service installation costs

被引：17

作者：

Xu, Dachuan ^{[1
]}

Zhang, Shuzhong ^{[2
]}

机构：

[1] Beijing Univ Technol, Dept Appl Math, Beijing 100022, Peoples R China

[2] Chinese Univ Hong Kong, Dept Syst Engn & Engn Management, Shatin, Hong Kong, Peoples R China

来源：

OPERATIONS RESEARCH LETTERS | 2008年 / 36卷 / 01期

基金：

中国国家自然科学基金;

关键词：

facility location; approximation algorithm; linear programming relaxation;

D O I：

10.1016/j.orl.2007.04.002

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

In this paper, we study the uncapacitated facility location problem with service installation costs depending on the type of service required. We propose a polynomial-time approximation algorithm with approximation ratio 1.808 which improves the previous approximation ratio of 2.391 of Shmoys, Swamy, and Levi. (c) 2007 Elsevier B.V. All rights reserved.

引用

页码：46 / 50

页数：5

共 17 条

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

BYRKA J, 2006, OPER RES LETT

[4]

BYRKA J, 2007, ARXIVCS0703010

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

Charikar, M ;

Guha, S .

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

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

Chudak, FA ;

Shmoys, DB .

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

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

Guha, S ;

Khuller, S .

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

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

[9]

Jain K., 2002, P THIRY 4 ANN ACM S, P731, DOI [10.1145/509907.510012, DOI 10.1016/J.0RL.2006.03.0]

[10]

Mahdian M, 2006, SIAM J COMPUT, V36, P411, DOI 10.1137/S0097539703435716

← 1 2 →