The week's pick
Random Articles
Reseach Article
Approximation Algorithm for Facility Location Problems
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 67 - Number 11 |
| Year of Publication: 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
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