A new approximation algorithm for the k-facility location problem

被引：75
作者：
Zhang, Peng
机构：
[1] Chinese Acad Sci, Inst Software, State Key Lab Comp Sci, Beijing 100080, Peoples R China
[2] Grad Univ Chinese Acad Sci, Beijing, Peoples R China
来源：
THEORETICAL COMPUTER SCIENCE | 2007年 / 384卷 / 01期
基金：
中国国家自然科学基金;
关键词：
facility location; k-median; local search; approximation algorithm;
D O I：
10.1016/j.tcs.2007.05.024
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
The k-facility location problem is a common generalization of the facility location and the k-median problems. For the metric uncapacitated k-facility location problem, we propose a polynomial-time 2 + root 3 + epsilon-approximation algorithm using the local search approach, which significantly improves the previously known approximation ratio 4, given by Jain et al. using the greedy method [K. Jain, M. Mahdian, E. Markakis, A. Saberi, V. Vazirani, Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP, Journal of the ACM 50 (2003) 795-824]. (c) 2007 Elsevier B.V. All rights reserved.
引用
收藏
页码：126 / 135
页数：10
相关论文
共 16 条
[1]  
[Anonymous], 1999, 40 ANN S FDN COMP SC
[2]   Local search heuristics for k-median and facility location problems [J].
Arya, V ;
Garg, N ;
Khandekar, R ;
Meyerson, A ;
Munagala, K ;
Pandit, V .
SIAM JOURNAL ON COMPUTING, 2004, 33 (03) :544-562
[3]  
BEASLEY J, 2005, OPERATIONS RES LIB
[4]   Hierarchical placement and network design problems [J].
Guha, S ;
Meyerson, A ;
Munagala, K .
41ST ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 2000, :603-612
[5]   Greedy strikes back: Improved facility location algorithms [J].
Guha, S ;
Khuller, S .
JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 1999, 31 (01) :228-248
[6]   The facility location problem with general cost functions [J].
Hajiaghayi, MT ;
Mahdian, M ;
Mirrokni, VS .
NETWORKS, 2003, 42 (01) :42-47
[7]   Greedy facility location algorithms analyzed using,dual fitting with factor-revealing LP [J].
Jain, K ;
Mahdian, M ;
Markakis, E ;
Saberi, A ;
Vazirani, VV .
JOURNAL OF THE ACM, 2003, 50 (06) :795-824
[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]   Analysis of a local search heuristic for facility location problems [J].
Korupolu, MR ;
Plaxton, CG ;
Rajaraman, R .
JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 2000, 37 (01) :146-188
12