Kamal Jain
Mohammad Mahdian
ABSTRACT
We present a simple and natural greedy algorithm for the metric uncapacitated facility location problem achieving an approximation guarantee of 1.61. We use this algorithm to find better approximation algorithms for the capacitated facility location problem with soft capacities and for a common generalization of the k-median and facility location problems. We also prove a lower bound of 1+2/e on the approximability of the k-median problem. At the end, we present a discussion about the techniques we have used in the analysis of our algorithm, including a computer-aided method for proving bounds on the approximation factor.
- M. Andrews and L. Zhang. The access network design problem. In Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, 1998.]] Google Scholar
Digital Library
- V. Arya, N. Garg, R. Khandekar, A. Meyerson, K. Munagala, and V. Pandit. Local search heuristics for k-median and facility location problems. In Proceedings of 33rd ACM Symposium on Theory of Computing, 2001.]] Google ScholarDigital Library
- M. L. Balinski. On finding integer solutions to linear programs. In Proc. IBM Scientific Computing Symposium on Combinatorial Problems, pages 225--248, 1966.]]Google Scholar
- M. Charikar and S. Guha. Improved combinatorial algorithms for facility location and k-median problems. In Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, pages 378--388, October 1999.]] Google ScholarDigital Library
- M. Charikar, S. Guha, E. Tardos, and D.B. Shmoys. A constant-factor approximation algorithm for the k-median problem. In Proceedings of the 31st Annual ACM Symposium on Theory of Computing, pages 1--10, May 1999.]] Google ScholarDigital Library
- M. Charikar, S. Khuller, D. Mount, and G. Narasimhan. Facility location with outliers. In 12th Annual ACM-SIAM Symposium on Discrete Algorithms, Washington DC, January 2001.]] Google ScholarDigital Library
- F.A. Chudak. Improved approximation algorithms for uncapacited facility location. In R.E. Bixby, E.A. Boyd, and R.Z. Ríos-Mercado, editors, Integer Programming and Combinatorial Optimization}, volume 1412 of Lecture Notes in Computer Science, pages 180--194. Springer, Berlin, 1998.]]Google Scholar
- F.A. Chudak and D. Shmoys. Improved approximation algorithms for the uncapacitated facility location problem. unpublished manuscript, 1998.]]Google Scholar
- G. Cornuejols, G.L. Nemhauser, and L.A. Wolsey. The uncapacitated facility location problem. In P. Mirchandani and R. Francis, editors, Discrete Location Theory, pages 119--171. John Wiley and Sons Inc., 1990.]]Google Scholar
- U. Feige. A threshold of ln n for approximating set cover. J. ACM, 45:634--652, 1998.]] Google ScholarDigital Library
- M. Goemans and J. Kleinberg. An improved approximation ratio for the minimum latency problem. (MATH)ematical Programming, 82:111--124, 1998.]]Google Scholar
- S. Guha. Approximation algorithms for facility location problems. PhD thesis, Stanford University, 2000.]] Google ScholarDigital Library
- S. Guha and S. Khuller. Greedy strikes back: Improved facility location algorithms. Journal of Algorithms, 31:228--248, 1999.]] Google ScholarDigital Library
- S. Guha, A. Meyerson, and K. Munagala. Hierarchical placement and network design problems. In Proceedings of the 41th Annual IEEE Symposium on Foundations of Computer Science, 2000.]] Google ScholarDigital Library
- S. Guha, A. Meyerson, and K. Munagala. Improved combinatorial algorithms for single sink edge installation problems. Technical Report STAN-CS-TN00 -96, Stanford University, 2000.]] Google ScholarDigital Library
- D. S. Hochbaum. Heuristics for the fixed cost median problem. (MATH)ematical Programming, 22(2):148--162, 1982.]]Google Scholar
- K. Jain, M. Mahdian, E. Markakis, A. Saberi, and V.V. Vazirani. Approximation algorithms for facility location via dual fitting with factor-revealing lp. submitted to Combinatorica.]]Google Scholar
- K. Jain and V.V. Vazirani. Primal-dual approximation algorithms for metric facility location and k-median problems. In Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, pages 2--13, October 1999.]] Google ScholarDigital Library
- S. Jamin, C. Jin, Y. Jin, D. Raz, Y. Shavitt, and L. Zhang. On the placement of internet instrumentations. In Proceedings of IEEE INFOCOM'00, pages 26--30, March 2000.]]Google ScholarCross Ref
- M.R. Korupolu, C.G. Plaxton, and R. Rajaraman. Analysis of a local search heuristic for facility location problems. In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1--10, January 1998.]] Google ScholarDigital Library
- A.A. Kuehn and M.J. Hamburger. A heuristic program for locating warehouses. Management Science, 9:643--666, 1963.]]Google ScholarDigital Library
- B. Li, M. Golin, G. Italiano, Deng X., and K. Sohraby. On the optimal placement of web proxies in the internet. In Proceedings of IEEE INFOCOM'99, pages 1282--1290, 1999.]]Google Scholar
- M. Mahdian, E. Markakis, A. Saberi, and V.V. Vazirani. A greedy facility location algorithm analyzed using dual fitting. In Proceedings of 5th International Workshop on Randomization and Approximation Techniques in Computer Science, volume 2129 of Lecture Notes in Computer Science, pages 127--137. Springer-Verlag, 2001.]] Google ScholarDigital Library
- M. Mahdian, Y. Ye, and J. Zhang. Improved approximation algorithms for metric facility location problems. Unpublished manuscript, 2002.]]Google Scholar
- R.J. McEliece, E.R. Rodemich, H. Rumsey Jr., and L.R. Welch. New upper bounds on the rate of a code via the delsarte-macwilliams inequalities. IEEE Transactions on Information Theory, 23:157--166, 1977.]]Google ScholarDigital Library
- L. Qiu, V.N. Padmanabhan, and G. Voelker. On the placement of web server replicas. In Proceedings of IEEE INFOCOM'01, Anchorage, AK, USA, April 2001.]]Google Scholar
- D.B. Shmoys. Approximation algorithms for facility location problems. In K. Jansen and S. Khuller, editors, Approximation Algorithms for Combinatorial Optimization, volume 1913 of Lecture Notes in Computer Science, pages 27--33. Springer, Berlin, 2000.]] Google ScholarDigital Library
- D.B. Shmoys, E. Tardos, and K.I. Aardal. Approximation algorithms for facility location problems. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing, pages 265--274, 1997.]] Google ScholarDigital Library
- M. Sviridenko. An 1.582-approximation algorithm for the metric uncapacitated facility location problem. to appear in the Ninth Conference on Integer Programming and Combinatorial Optimization, 2002.]] Google ScholarDigital Library
- M. Thorup. Quick k-median, k-center, and facility location for sparse graphs. In Automata, Languages and Programming, 28th International Colloquium, Crete, Greece, volume 2076 of Lecture Notes in Computer Science, pages 249--260, 2001.]] Google ScholarDigital Library
- V. V. Vazirani. Approximation Algorithms. Springer-Verlag, Berlin, 2001.]] Google ScholarDigital Library
Index Terms
- A new greedy approach for facility location problems
Recommendations
Approximating the two-level facility location problem via a quasi-greedy approach
We propose a quasi-greedy algorithm for approximating the classical uncapacitated 2-level facility location problem (2-LFLP). Our algorithm, unlike the standard greedy algorithm, selects a sub-optimal candidate at each step. It also relates the ...
Improved Combinatorial Algorithms for Facility Location Problems
We present improved combinatorial approximation algorithms for the uncapacitated facility location problem. Two central ideas in most of our results are cost scaling and greedy improvement. We present a simple greedy local search algorithm which ...
Comments