Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
作者： Kamal Jain , Mohammad Mahdian , Evangelos Markakis , Amin Saberi , Vijay V. Vazirani
关键词:
摘要: … most of the dominant ideas in approximation algorithms (see Vazirani [2001]). Perhaps the … as in Jain and Vazirani [1999] to give a factor 3-approximation algorithm for this problem …
arxiv.org
acm.org
aueb.gr 
sci-hub.se 参考文章(48)
M. Charikar, S. Guha, Improved combinatorial algorithms for the facility location and k-median problems foundations of computer science. pp. 378- 388 ,(1999) , 10.1109/SFFCS.1999.814609
John F. Stollsteimer, A Working Model for Plant Numbers and Locations Journal of Farm Economics. ,vol. 45, pp. 631- 645 ,(1963) , 10.2307/1235442
K. Jain, V.V. Vazirani, Primal-dual approximation algorithms for metric facility location and k-median problems foundations of computer science. pp. 2- 13 ,(1999) , 10.1109/SFFCS.1999.814571
Laurence A. Wolsey, George L. Nemhauser, Integer and Combinatorial Optimization ,(1988)
Fabián A. Chudak, David B. Shmoys, Improved Approximation Algorithms for the Uncapacitated Facility Location Problem SIAM Journal on Computing. ,vol. 33, pp. 1- 25 ,(2004) , 10.1137/S0097539703405754
Sridhar Rajagopalan, Vijay V. Vazirani, Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs SIAM Journal on Computing. ,vol. 28, pp. 525- 540 ,(1998) , 10.1137/S0097539793260763
Moses Charikar, Samir Khuller, Giri Narasimhan, David M. Mount, Algorithms for facility location problems with outliers symposium on discrete algorithms. pp. 642- 651 ,(2001) , 10.5555/365411.365555
Kamal Jain, Mohammad Mahdian, Amin Saberi, A new greedy approach for facility location problems symposium on the theory of computing. pp. 731- 740 ,(2002) , 10.1145/509907.510012
Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala, Vinayaka Pandit, Local search heuristic for k-median and facility location problems Proceedings of the thirty-third annual ACM symposium on Theory of computing - STOC '01. pp. 21- 29 ,(2001) , 10.1145/380752.380755
Sudipto Guha, Adam Meyerson, Kamesh Munagala, Improved algorithms for fault tolerant facility location symposium on discrete algorithms. pp. 636- 641 ,(2001) , 10.5555/365411.365554