research-article

Facility location with hierarchical facility costs

Authors:

ÉVA TardosAuthors Info & Claims

ACM Transactions on Algorithms (TALG), Volume 6, Issue 2

Article No.: 37, Pages 1 - 22

https://doi.org/10.1145/1721837.1721853

Published: 06 April 2010 Publication History

Abstract

We introduce a facility location problem with submodular facility cost functions, and give an O(log n) approximation algorithm for it. Then we focus on a special case of submodular costs, called hierarchical facility costs, and give a (4.237 + ϵ)-approximation algorithm using local search. The hierarchical facility costs model multilevel service installation. Shmoys et al. [2004] gave a constant factor approximation algorithm for a two-level version of the problem. Here we consider a multilevel problem, and give a constant factor approximation algorithm, independent of the number of levels, for the case of identical costs on all facilities.

References

[1]

Arya, V., Garg, N., Khandekar, R., Meyerson, A., Munagala, K., and Pandit, V. 2004. Local search heuristics for k-median and facility location problems. SIAM J. Comput. 33, 3, 544--562.

Digital Library

[2]

Byrka, J. 2007. An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem. In Proceedings of the 10th APPROX. 29--43.

Digital Library

[3]

Charikar, M., and Guha, S. 2005. Improved combinatorial algorithms for facility location problems. SIAM J. Comput. 34, 4, 803--824.

Digital Library

[4]

Chudak, F. A. 1998. Improved approximation algorithms for uncapitated facility location. In IPCO. 180--194.

[5]

Chudak, F. A., and Shmoys, D. B. 2003. Improved approximation algorithms for the uncapacitated facility location problem. SIAM J. Comput. 33, 1, 1--25.

Digital Library

[6]

Drezner, Z. 1995. Facility Location: A Survey of Applications and Methods. Springer-Verlag, New York.

[7]

Garg, N., Khandekar, R., and Pandit, V. 2005. Improved approximation for universal facility location. In Proceedings of the 16th ACM Symposium on Discrete Algorithms. ACM, New York, 959--960.

Digital Library

[8]

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

Digital Library

[9]

Hajiaghayi, M. T., Mahdian, M., and Mirrokni, V. S. 2003. The facility location problem with general cost functions. Networks 42, 42--47.

[10]

Hayrapetyan, A., Swamy, C., and Tardos, E. 2005. Network design for information networks. In Proceedings of the 16th ACM Symposium on Discrete Algorithms. ACM, New York, 933--942.

Digital Library

[11]

Hochbaum, D. S. 1982. Heuristics for the fixed cost median problem. Math. Programming 22, 1, 148--162.

Digital Library

[12]

Iwata, S., Fleischer, L., and Fujishige, S. 2001. A combinatorial strongly polynomial algorithm for minimizing submodular functions. J. ACM 48, 4, 761--777.

Digital Library

[13]

Jain, K., and Vazirani, V. V. 2001. Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and lagrangian relaxation. J. ACM 48, 2, 274--296.

Digital Library

[14]

Korupolu, M. R., Plaxton, C. G., and Rajaraman, R. 2000. Analysis of a local search heuristic for facility location problems. J. Algorithms 37, 1, 146--188.

Digital Library

[15]

Mahdian, M., and Pál, M. 2003. Universal facility location. In Proceedings of the European Symposium on Algorithms. 409--421.

[16]

Ravi, R., and Sinha, A. 2004. Multicommodity facility location. In Proceedings of the 15th ACM Symposium on Discrete Algorithms. ACM, New York, 342--349.

Digital Library

[17]

Schrijver, A. 2000. A combinatorial algorithm minimizing submodular functions in strongly polynomial time. J. Combinat. Theory, Ser. B 80, 2, 346--355.

Digital Library

[18]

Shmoys, D., Swamy, C., and Levi, R. 2004. Facility location with service installation costs. In Proceedings of the 15th ACM Symposium on Discrete Algorithms. ACM, New York, 1088--1097.

Digital Library

[19]

Shmoys, D. B., Tardos, E., and Aardal, K. 1997. Approximation algorithms for facility location problems. In Proceedings of the 29th ACM Symposium on Theory of Computing. ACM, New York, 265--274.

Digital Library

[20]

Sviridenko, M. 2002. An improved approximation algorithm for the metric uncapacitated facility location problem. In IPCO. 240--257.

Digital Library

[21]

Vazirani, V. V. 2001. Approximation algorithms. Springer-Verlag, Berlin, Germany.

Digital Library

[22]

von Rickenbach, P., and Wattenhofer, R. 2004. Gathering correlated data in sensor networks. In DIALM-POMC '04: Proceedings of the 2004 Joint Workshop on Foundations of Mobile Computing. 60--66.

Digital Library

[23]

Vygen, J. 2005. Approximation algorithms for facility location problems (lecture notes). Tech. Rep. 05950-OR. http://www.or.uni-bonn.de/~vygen/fl.pdf.

Cited By

Castenow JFeldkord BKnollmann TMalatyali MMeyer Auf der Heide FScheideler CSpear M(2020)The Online Multi-Commodity Facility Location ProblemProceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3350755.3400281(129-139)Online publication date: 6-Jul-2020
https://dl.acm.org/doi/10.1145/3350755.3400281
Krishnaswamy RSviridenko M(2016)Inapproximability of the Multilevel Uncapacitated Facility Location ProblemACM Transactions on Algorithms10.1145/290705013:1(1-25)Online publication date: 21-Sep-2016
https://dl.acm.org/doi/10.1145/2907050
Cheung MElmachtoub ALevi RShmoys D(2016)The submodular joint replenishment problemMathematical Programming: Series A and B10.1007/s10107-015-0920-3158:1-2(207-233)Online publication date: 1-Jul-2016
https://dl.acm.org/doi/10.1007/s10107-015-0920-3
Show More Cited By

Index Terms

Facility location with hierarchical facility costs
1. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Routing and network design problems

Recommendations

A local search approximation algorithm for a squared metric k-facility location problem

In this paper, we introduce a squared metric k-facility location problem (SM-k-FLP) which is a generalization of the squared metric facility location problem and k-facility location problem (k-FLP). In the SM-k-FLP, we are given a client set $$\mathcal {...
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 ...
Approximating soft-capacitated facility location problem with uncertainty

In this paper we devise the stochastic and robust approaches to study the soft-capacitated facility location problem with uncertainty. We first present a new stochastic soft-capacitated model called The 2-Stage Soft Capacitated Facility Location ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Algorithms

ACM Transactions on Algorithms Volume 6, Issue 2

March 2010

373 pages

ISSN:1549-6325

EISSN:1549-6333

DOI:10.1145/1721837

Issue’s Table of Contents

Copyright © 2010 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: 06 April 2010

Accepted: 01 March 2008

Received: 01 August 2007

Published in TALG Volume 6, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
701
Total Downloads

Downloads (Last 12 months)29
Downloads (Last 6 weeks)4

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Castenow JFeldkord BKnollmann TMalatyali MMeyer Auf der Heide FScheideler CSpear M(2020)The Online Multi-Commodity Facility Location ProblemProceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3350755.3400281(129-139)Online publication date: 6-Jul-2020
https://dl.acm.org/doi/10.1145/3350755.3400281
Krishnaswamy RSviridenko M(2016)Inapproximability of the Multilevel Uncapacitated Facility Location ProblemACM Transactions on Algorithms10.1145/290705013:1(1-25)Online publication date: 21-Sep-2016
https://dl.acm.org/doi/10.1145/2907050
Cheung MElmachtoub ALevi RShmoys D(2016)The submodular joint replenishment problemMathematical Programming: Series A and B10.1007/s10107-015-0920-3158:1-2(207-233)Online publication date: 1-Jul-2016
https://dl.acm.org/doi/10.1007/s10107-015-0920-3
Ahmadian SFriggstad ZSwamy CKhanna S(2013)Local-search based approximation algorithms for mobile facility location problemsProceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms10.5555/2627817.2627932(1607-1621)Online publication date: 6-Jan-2013
https://dl.acm.org/doi/10.5555/2627817.2627932
Li YShu JWang XXiu NXu DZhang J(2013)Approximation Algorithms for Integrated Distribution Network Design ProblemsINFORMS Journal on Computing10.1287/ijoc.1120.052225:3(572-584)Online publication date: 1-Jul-2013
https://dl.acm.org/doi/10.1287/ijoc.1120.0522
Krishnaswamy RSviridenko M(2012)Inapproximability of the multi-level uncapacitated facility location problemProceedings of the twenty-third annual ACM-SIAM symposium on Discrete algorithms10.5555/2095116.2095175(718-734)Online publication date: 17-Jan-2012
https://dl.acm.org/doi/10.5555/2095116.2095175
Chekuri CEne A(2011)Submodular cost allocation problem and applicationsProceedings of the 38th international colloquim conference on Automata, languages and programming - Volume Part I10.5555/2027127.2027165(354-366)Online publication date: 4-Jul-2011
https://dl.acm.org/doi/10.5555/2027127.2027165
Chekuri CEne A(2011)Submodular Cost Allocation Problem and ApplicationsAutomata, Languages and Programming10.1007/978-3-642-22006-7_30(354-366)Online publication date: 2011
https://doi.org/10.1007/978-3-642-22006-7_30

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