article

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

Authors:

Mohammad Mahdian,

Evangelos Markakis,

Vijay V. VaziraniAuthors Info & Claims

Journal of the ACM (JACM), Volume 50, Issue 6

Pages 795 - 824

https://doi.org/10.1145/950620.950621

Published: 01 November 2003 Publication History

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.]]

Digital Library

[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.]]

Digital Library

[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.]]

Digital Library

[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]]

Digital Library

[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.]]

Digital Library

[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.]]

Digital Library

[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.]]

Digital Library

[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.]]

Digital Library

[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.]]

Digital Library

[16]

Guha, S. 2000. Approximation algorithms for facility location problems. PhD dissertation, Stanford Univ., Stanford, Calif.]]

Digital Library

[17]

Guha, S., and Khuller, S. 1999. Greedy strikes back: Improved facility location algorithms. J. Algorithms 31, 228--248.]]

Digital Library

[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.]]

Digital Library

[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.]]

Digital Library

[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.]]

Digital Library

[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.]]

Digital Library

[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.]]

Digital Library

[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.]]

Digital Library

[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.]]

Digital Library

[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.]]

Digital Library

[29]

Kuehn, A. A., and Hamburger, M. J. 1963. A heuristic program for locating warehouses. Manag. Sci. 9, 643--666.]]

Digital Library

[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.]]

Digital Library

[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).]]

Digital Library

[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.]]

Digital Library

[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.]]

Digital Library

[35]

Nemhauser, G. L., and Wolsey, L. A. 1990. Integer and Combinatorial Optimization. Wiley, New York.]]

Digital Library

[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.]]

Digital Library

[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.]]

Digital Library

[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.]]

Digital Library

[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.]]

Digital Library

[43]

Vazirani, V. V. 2001. Approximation Algorithms. Springer-Verlag, Berlin, Germany.]]

Digital Library

[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.]]

Cited By

Miao RWu CYuan J(2025)LP-Rounding Based Algorithm for Capacitated Uniform Facility Location Problem with Soft PenaltiesTsinghua Science and Technology10.26599/TST.2024.901004030:1(279-289)Online publication date: Feb-2025
https://doi.org/10.26599/TST.2024.9010040
Manurangsi P(2025)Improved lower bound for differentially private facility locationInformation Processing Letters10.1016/j.ipl.2024.106502187(106502)Online publication date: Jan-2025
https://doi.org/10.1016/j.ipl.2024.106502
Luo HHan LShuai TWang F(2024)Approximation and Heuristic Algorithms for the Priority Facility Location Problem with OutliersTsinghua Science and Technology10.26599/TST.2023.901015229:6(1694-1702)Online publication date: Dec-2024
https://doi.org/10.26599/TST.2023.9010152
Show More Cited By

Index Terms

Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
      1. Combinatorial algorithms
    2. Graph theory
      1. Network flows
2. Theory of computation
  1. Design and analysis of algorithms
    1. Graph algorithms analysis
      1. Network flows
  2. Randomness, geometry and discrete structures

Recommendations

Approximation algorithms for metric facility location and k-Median problems using the primal-dual schema and Lagrangian relaxation

We present approximation algorithms for the metric uncapacitated facility location problem and the metric k-median problem achieving guarantees of 3 and 6 respectively. The distinguishing feature of our algorithms is their low running time: O(m logm) ...
An LP rounding algorithm for approximating uncapacitated facility location problem with penalties

In this paper, we consider an interesting variant of the facility location problem called uncapacitated facility location problem with penalties (UFLWP, for short) in which each client can be either assigned to some opened facility or rejected by paying ...
Approximation Algorithms for Metric Facility Location Problems

In this paper we present a 1.52-approximation algorithm for the metric uncapacitated facility location problem, and a 2-approximation algorithm for the metric capacitated facility location problem with soft capacities. Both these algorithms improve the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 50, Issue 6

November 2003

186 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/950620

Issue’s Table of Contents

Copyright © 2003 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 November 2003

Published in JACM Volume 50, Issue 6

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

359
Total Citations
View Citations
3,202
Total Downloads

Downloads (Last 12 months)69
Downloads (Last 6 weeks)9

Reflects downloads up to 02 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Miao RWu CYuan J(2025)LP-Rounding Based Algorithm for Capacitated Uniform Facility Location Problem with Soft PenaltiesTsinghua Science and Technology10.26599/TST.2024.901004030:1(279-289)Online publication date: Feb-2025
https://doi.org/10.26599/TST.2024.9010040
Manurangsi P(2025)Improved lower bound for differentially private facility locationInformation Processing Letters10.1016/j.ipl.2024.106502187(106502)Online publication date: Jan-2025
https://doi.org/10.1016/j.ipl.2024.106502
Luo HHan LShuai TWang F(2024)Approximation and Heuristic Algorithms for the Priority Facility Location Problem with OutliersTsinghua Science and Technology10.26599/TST.2023.901015229:6(1694-1702)Online publication date: Dec-2024
https://doi.org/10.26599/TST.2023.9010152
Ekbatani FFeng YKash INiazadeh R(2024)Online Job AssignmentSSRN Electronic Journal10.2139/ssrn.4745629Online publication date: 2024
https://doi.org/10.2139/ssrn.4745629
Dütting PLattanzi SPaes Leme RVassilvitskii S(2024)Secretaries with AdviceMathematics of Operations Research10.1287/moor.2023.138449:2(856-879)Online publication date: 1-May-2024
https://dl.acm.org/doi/10.1287/moor.2023.1384
Etesami SChua TNgo CKa-Wei Lee RKumar RLauw H(2024)Distributed Data Placement and Content Delivery in Web Caches with Non-Metric Access CostsProceedings of the ACM Web Conference 202410.1145/3589334.3645654(4340-4351)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1145/3589334.3645654
Ikeda HTakanaga T(2024)Problem Definition and Optimization Method for Bipartite Graph SchedulingIEEE Access10.1109/ACCESS.2024.341305112(83675-83683)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3413051
Chen LChen ZWan LLuo W(2024)Approximation Scheme for the Single-Client Capacitated Facility Location Problem With Operational Cost Budget ConstraintJournal of the Operations Research Society of China10.1007/s40305-024-00555-yOnline publication date: 3-Oct-2024
https://doi.org/10.1007/s40305-024-00555-y
Guo YLi Q(2024)Approximation algorithms for the fault-tolerant facility location problem with submodular penaltiesJournal of Combinatorial Optimization10.1007/s10878-024-01106-047:2Online publication date: 26-Feb-2024
https://dl.acm.org/doi/10.1007/s10878-024-01106-0
Caragiannis IFilos-Ratsikas AFrederiksen SHansen KTan Z(2024)Truthful facility assignment with resource augmentation: an exact analysis of serial dictatorshipMathematical Programming: Series A and B10.1007/s10107-022-01902-8203:1-2(901-930)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1007/s10107-022-01902-8
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents