Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP

Abstract

In this article, we will formalize the method of dual fitting and the idea of factor-revealing LP. This combination is used to design and analyze two greedy algorithms for the metric uncapacitated facility location problem. Their approximation factors are 1.861 and 1.61, with running times of O(m log m) and O(n³), respectively, where n is the total number of vertices and m is the number of edges in the underlying complete bipartite graph between cities and facilities. The algorithms are used to improve recent results for several variants of the problem.

References

1. Andrews, M., and Zhang, L. 1998. The access network design problem. In Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif.]]
2. Arya, V., Garg, N., Khandekar, R., Meyerson, A., Munagala, K., and Pandit, V. 2001. Local search heuristics for k-median and facility location problems. In Proceedings of 33rd ACM Symposium on Theory of Computing. ACM, New York.]]
3. Balinski, M. L. 1966. On finding integer solutions to linear programs. In Proceedings of the IBM Scientific Computing Symposium on Combinatorial Problems. 225--248.]]
4. Beasley, J. E. 2002. Operations research library. http://mscmga.ms.ic.ac.uk/info.html.]]
5. Cameron, C. W., Low, S. H., and Wei, D. X. 2002. High-density model for server allocation and placement. In Proceedings of the 2000 ACM SIG Metrics. ACM, New York, pp. 152--159.]]
6. Charikar, M., and Guha, S. 1999. Improved combinatorial algorithms for facility location and k-median problems. In Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., 378--388]]
7. Charikar, M., Guha, S., Tardos, E., and Shmoys, D. B. 1999. A constant-factor approximation algorithm for the k-median problem. In Proceedings of the 31st Annual ACM Symposium on Theory of Computing. ACM, New York, 1--10.]]
8. Charikar, M., Khuller, S., Mount, D., and Narasimhan, G. 2001. Facility location with outliers. In 12th Annual ACM-SIAM Symposium on Discrete Algorithms (Washington DC). ACM, New York.]]
9. Chudak, F. A. 1998. Improved approximation algorithms for uncapacitated facility location. In Integer Programming and Combinatorial Optimization, R. E. Bixby, E. A. Boyd, and R. Z. Ríos-Mercado, Eds. Lecture Notes in Computer Science, vol. 1412. Springer-Verlag, Berlin, Germany, Berlin, Germany, 180--194.]]
10. Chudak, F. A., and Shmoys, D. 1998. Improved approximation algorithms for the uncapacitated facility location problem. Unpublished manuscript.]]
11. Chvatal, V. 1979. A greedy heuristic for the set covering problem. Math. Oper. Res. 4, 233--235.]]
12. Cornuejols, G., Nemhauser, G. L., and Wolsey, L. A. 1990. The uncapacitated facility location problem. In Discrete Location Theory, P. Mirchandani and R. Francis, Eds. Wiley, New York, 119--171.]]
13. Devanur, N., Mihail, M., and Vazirani, V. V. 2003. Strategyproof mechanisms for facility location and set cover games via the method of dual fitting. In Proceeding of the ACM Conference on Electronic Commerce. ACM, New York.]]
14. Goemans, M., and Kleinberg, J. 1998. An improved approximation ratio for the minimum latency problem. Math. Prog. 82, 111--124.]]
15. Goemans, M. X., and Skutella, M. 2000. Cooperative facility location games. In Proceedings of the Symposium on Discrete Algorithms. 76--85.]]
16. Guha, S. 2000. Approximation algorithms for facility location problems. PhD dissertation, Stanford Univ., Stanford, Calif.]]
17. Guha, S., and Khuller, S. 1999. Greedy strikes back: Improved facility location algorithms. J. Algorithms 31, 228--248.]]
18. Guha, S., Meyerson, A., and Munagala, K. 2000a. Hierarchical placement and network design problems. In Proceedings of the 41th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif.]]
19. Guha, S., Meyerson, A., and Munagala, K. 2000b. Improved combinatorial algorithms for single sink edge installation problems. Tech. Rep. STAN-CS-TN00 -96, Stanford Univ. Stanford, Calif.]]
20. Guha, S., Meyerson, A., and Munagala, K. 2001. Improved algorithms for fault tolerant facility location. In Proceedings of the Symposium on Discrete Algorithms. 636--641.]]
21. Hajiaghayi, M., Mahdian, M., and Mirrokni, V. 2003. The facility location problem with general cost functions. Networks 42, 1 (Aug.), 42--47.]]
22. Hochbaum, D. S. 1982. Heuristics for the fixed cost median problem. Math. Prog. 22, 2, 148--162.]]
23. Jain, K., and Vazirani, V. V. 1999. 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. IEEE Computer Society Press, Los Alamitos, Calif. 2--13.]]
24. Jain, K., and Vazirani, V. V. 2000. An approximation algorithm for the fault tolerant metric facility location problem. In Approximation Algorithms for Combinatorial Optimization, Proceedings of APPROX 2000, K. Jansen and S. Khuller, Eds. Lecture Notes in Computer Science, vol. 1913. Springer-Verlag, New York, 177--183.]]
25. Jain, K., and Vazirani, V. V. 2001. Applications of approximation algorithms to cooperative games. In Proceedings of the ACM Symposium on Theory of Computing. ACM, New York, 364--372.]]
26. Jamin, S., Jin, C., Jin, Y., Raz, D., Shavitt, Y., and Zhang, L. 2000. On the placement of internet instrumentations. In Proceedings of IEEE INFOCOM'00. IEEE Computer Society Press, Los Alamitos, Calif. 26--30.]]
27. Kaufman, L., van Eede, M., and Hansen, P. 1977. A plant and warehouse location problem. Oper. Res. Quart. 28, 547--557.]]
28. Korupolu, M. R., Plaxton, C. G., and Rajaraman, R. 1998. Analysis of a local search heuristic for facility location problems. In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, 1--10.]]
29. Kuehn, A. A., and Hamburger, M. J. 1963. A heuristic program for locating warehouses. Manag. Sci. 9, 643--666.]]
30. Li, B., Golin, M., Italiano, G., Deng, X., and Sohraby, K. 1999. On the optimal placement of web proxies in the internet. In Proceedings of IEEE INFOCOM'99. IEEE Computer Society Press, Los Alamitos, Calif., 1282--1290.]]
31. Lovasz, L. 1975. On the ratio of optimal integral and fractional covers. Disc. Math. 13, 383--390.]]
32. Mahdian, M., Ye, Y., and Zhang, J. 2002. Improved approximation algorithms for metric facility location problems. In Proceedings of 5th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX 2002).]]
33. McEliece, R. J., Rodemich, E. R., Rumsey Jr., H., and Welch, L. R. 1977. New upper bounds on the rate of a code via the delsarte-macwilliams inequalities. IEEE Trans. Inf. Theory 23, 157--166.]]
34. Mettu, R. R., and Plaxton, G. 2000. The online median problem. In Proceedings of the IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., 339--348.]]
35. Nemhauser, G. L., and Wolsey, L. A. 1990. Integer and Combinatorial Optimization. Wiley, New York.]]
36. Qiu, L., Padmanabhan, V. N., and Voelker, G. M. 2001. On the placement of web server replicas. In Proceedings of IEEE INFOCOM (Anchorage, Ak.). IEEE Computer Society Press, Los Alamitos, Calif., 1587--1596.]]
37. Rajagopalan, S., and Vazirani V. V. 1999. Primal-dual RNC approximation algorithms for set cover and covering integer programs. SIAM J. Comput. 28, 2, 525--540.]]
38. Shmoys, D. B., Tardos, E., and Aardal, K. I. 1997. Approximation algorithms for facility location problems. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing. ACM, New York, 265--274.]]
39. Stollsteimer, J. F. 1961. The effect of technical change and output expansion on the optimum number, size and location of pear marketing facilities in a California pear producing region. PhD dissertation. University of California at Berkeley.]]
40. Stollsteimer, J. F. 1963. A working model for plant numbers and locations. J. Farm Econom. 45, 631--645.]]
41. Sviridenko, M. 2002. An improved approximation algorithm for the metric uncapacitated facility location problem. In Proceedings of the Ninth Conference on Integer Programming and Combinatorial Optimization. 240--257.]]
42. Thorup, M. 2001. Quick k-median, k-center, and facility location for sparse graphs. In Automata, Languages and Programming, 28th International Colloquium (Crete, Greece). Lecture Notes in Computer Science, vol. 2076. Springer-Verlag, New York, 249--260.]]
43. Vazirani, V. V. 2001. Approximation Algorithms. Springer-Verlag, Berlin, Germany.]]
44. Zegura, E. W., Calvert, K. L., and Bhattacharjee, S. 1996. How to model an internetwork. In Proceedings of IEEE INFOCOM. Vol. 2 (San Francisco, Calif.) IEEE Computer Society Press, Los Alamitos, Calif. 594--602.]]

Index Terms

• Mathematics of computing

  • Discrete mathematics

    • Combinatorics

      • Combinatorial algorithms

    • Graph theory

      • Network flows

• Theory of computation

  • Design and analysis of algorithms

    • Graph algorithms analysis

      • Network flows

  • Randomness, geometry and discrete structures