Research Article
Approximation Algorithm for Facility Location Problems
|
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
|
| Volume 67 - Issue 11 |
| Published: April 2013 |
| Authors: Pawan Kumar Patel, Vivek Sharma |
10.5120/11436-6621
|
Pawan Kumar Patel, Vivek Sharma . Approximation Algorithm for Facility Location Problems. International Journal of Computer Applications. 67, 11 (April 2013), 1-5. DOI=10.5120/11436-6621
@article{ 10.5120/11436-6621,
author = { Pawan Kumar Patel,Vivek Sharma },
title = { Approximation Algorithm for Facility Location Problems },
journal = { International Journal of Computer Applications },
year = { 2013 },
volume = { 67 },
number = { 11 },
pages = { 1-5 },
doi = { 10.5120/11436-6621 },
publisher = { Foundation of Computer Science (FCS), NY, USA }
}
%0 Journal Article
%D 2013
%A Pawan Kumar Patel
%A Vivek Sharma
%T Approximation Algorithm for Facility Location Problems%T
%J International Journal of Computer Applications
%V 67
%N 11
%P 1-5
%R 10.5120/11436-6621
%I Foundation of Computer Science (FCS), NY, USA
Abstract
Significant research effort has been devoted in the study of approximation algorithms for NP-hard problems. In this work we modify a known primal-dual approximation algorithm for facility location problem. Although we fail to give a performance guarantee for the new approach but we show that our method performs better in a tight case.
References
- J. Stollsteimer, "A working model for plant numbers and locations," Journal of Farm Economics, vol. 45, pp. 631–645, 1963.
- A. A. Kuehn and M. J. Hamburger, "A heuristic program for locating warehouse," Management Science, vol. 9, pp. 643–666, 1963.
- A. Manne, "A plant location and economy of scale decentralization and computation," Management Science, vol. 11, pp. 213–235, 1964.
- G. Cornuejola, G. L. Nemhauser, and L. Wolsey, "The uncapacitated facility location problem," In P. Mirchandani and R. Francis editors Discrete Location Theory John Wiley and Sons New York, pp. 119–171, 1990.
- G. Guha and Khullar, "Greedy strikes back:improved facility location algorithms," Journal of Algorithms, vol. 31(1), pp. 228–248, 1990.
- M. Sviridenko, "Approximation algorithms for facility location problem," PhD thesis Stanford, 2000.
- D. Hochbaum, "Heuristics for the fixed cost median problem," Mathematical Programming, vol. 22), pp. 148–162, 1982.
- D. B. Shmoys, E. Tardos, and K. I. Aardal, "Approximation algorithms for facility location problems," In proceedings of the 29th Annual Symposium on Theory of Computing, pp. 265–274, 1997.
- K. Jain and V. V. Vazirani, "Approximation algorithm for metric facility location and k-median problems using primal-dual schema and lagrangian relaxation," ACM, vol. 48, March 2001.
- M. Mahdian, Y. Ye, and J. zhang, "A 1. 52 approximation algorithm for the uncapacitated facility location problem," Manuscript.
- J. Byrka, "An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem," Proceedings of the 10th International Workshop on Approximation and the 11th International Workshop on Randomization and combinatorial Optimization Algorithm and Techniques Berlin Heidelberg Springer -Verlag, pp. 29–43, 2007. 5
Index Terms
Keywords