research-article

Inapproximability of the multi-level uncapacitated facility location problem

Authors:

Ravishankar Krishnaswamy,

Maxim SviridenkoAuthors Info & Claims

SODA '12: Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete algorithms

Pages 718 - 734

Published: 17 January 2012 Publication History

Abstract

In this paper, we present improved inapproximability results for the k-level uncapacitated facility location problem. In particular, we show that there is no polynomial time approximation algorithm with performance guarantee better than 1.539 unless NP is contained in DTIME(n^{O(log log n)}) for the case when k = 2. For the case of general k (tendining to infinity) we obtain a better hardness factor of 1.61.

Interestingly, our results show that the two-level problem is computationally harder than the well known uncapacitated facility location problem (k = 1) since the best known approximation guarantee for the latter problem is 1.488 due to Li [22], and our inapproximability is a factor of 1.539 for the two-level problem. The only inapproximability result known before for this class of metric facility location problems is the bound of 1.463 due to Guha and Khuller [17], which holds even for the case of k = 1.

References

[1]

K. Aardal, F. Chudak and D. Shmoys, A 3-approximation algorithm for the k-level uncapacitated facility location problem, Inform. Process. Lett. 72 (1999), 161--167.

Digital Library

[2]

K. Aardal, M. Labbe, J. Leung and M. Queyranne, On the Two-Level Uncapacitated Facility Location Problem. INFORMS Journal on Computing 8(3): 289--301 (1996).

[3]

A. Ageev, Improved approximation algorithms for multilevel facility location problems, Oper. Res. Letters 30 (2002), 327--332.

Digital Library

[4]

A. Ageev and V. Beresnev, Polynomially solvable special cases of the simple plant location problem, in: R. Kannan and W. Pulleyblank (eds.), Proceedings of the First IPCO Conference, Waterloo University Press, Waterloo, 1990, 1--6.

Digital Library

[5]

A. Ageev, Y. Ye, and J. Zhang, Improved combinatorial approximation algorithms for the k-level facility location problem, SIAM J. Discrete Math. 18(1): 207--217 (2004).

Digital Library

[6]

A. Archer, Inapproximability of the asymmetric facility location and k-median problems, unpublished manuscript 2000.

[7]

A. Barros, Discrete and fractional programming techniques for location models. Combinatorial Optimization, 3. Kluwer Academic Publishers, Dordrecht, 1998.

[8]

A. Bumb and W. Kern, A simple dual ascent algorithm for the multilevel facility location problem. Approximation, randomization, and combinatorial optimization (Berkeley, CA, 2001), 55--62, Lecture Notes in Comput. Sci., 2129, Springer, Berlin, 2001.

Digital Library

[9]

J. Byrka and K. Aardal, An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem. SIAM J. Comput. 39(6): 2212--2231 (2010).

Digital Library

[10]

M. Charikar and S. Guha, Improved Combinatorial Algorithms for Facility Location Problems. SIAM J. Comput. 34(4): 803--824 (2005).

Digital Library

[11]

F. Chudak and D. Shmoys, Improved Approximation Algorithms for the Uncapacitated Facility Location Problem. SIAM J. Comput. 33(1): 1--25 (2003).

Digital Library

[12]

V. Chvatal, A greedy heuristic for the set-covering problem, Math. Oper. Res. 4 (1979), no. 3, 233235.

[13]

Facility location. Applications and theory. Edited by Zvi Drezner and Horst W. Hamacher. Springer-Verlag, Berlin, 2002.

[14]

U. Feige, A Threshold of ln n for Approximating Set Cover, Journal of ACM 45 (1998), 634--652.

Digital Library

[15]

A. Gabor and J. van Ommeren, A new approximation algorithm for the multilevel facility location problem, Discrete Applied Mathematics 158(5): 453--460 (2010).

Digital Library

[16]

S. Guha and S. Khuller, Greedy strikes back: improved facility location algorithms, Proceeding SODA '98 Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, pp. 649--657.

Digital Library

[17]

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

Digital Library

[18]

K. Jain, M. Mahdian, E. Markakis, A. Saberi and V. Vazirani, Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP. J. ACM 50(6): 795--824 (2003).

Digital Library

[19]

D. Johnson, Approximation algorithms for combinatorial problems, J. Comput. System Sci. 9 (1974), 256--278.

Digital Library

[20]

L. Kaufman, M. vanden Eede and P. Hansen. A plant and warehouse location problem. Operational Research Quarterly, 28:547--557, 1977.

[21]

J. Krarup and P. Pruzan, The simple plant location problem: survey and synthesis. European J. Oper. Res. 12 (1983), no. 1, 3681.

[22]

Shi Li, A 1.488-approximation algorithm for the uncapacitated facility location problem, to appear in ICALP 2011.

[23]

L. Lovász, On the ratio of optimal integral and fractional covers. Discrete Math. 13 (1975), no. 4, pp. 383--390.

[24]

M. Mahdian, Y. Ye, and J. Zhang, Improved Approximation Algorithms for Metric Facility Location Problems, APPROX 2002.

Digital Library

[25]

Discrete location theory. Edited by Pitu B. Mirchandani and Richard L. Francis. Wiley-Interscience Series in Discrete Mathematics and Optimization. A Wiley-Interscience Publication. John Wiley & Sons, Inc., New York, 1990.

[26]

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

Digital Library

[27]

D. Shmoys, The design and analysis of approximation algorithms: facility location as a case study. Trends in optimization, 85--97, Proc. Sympos. Appl. Math., 61, Amer. Math. Soc., Providence, RI, 2004.

[28]

M. Sviridenko, An Improved Approximation Algorithm for the Metric Uncapacitated Facility Location Problem, in Proceedings of the Conference on Integer Programming and Combinatorial Optimization (IPCO02), Lecture Notes in Computer Science v. 2337, pp.230--239.

Digital Library

[29]

Z. Svitkina and E. Tardos, Facility location with hierarchical facility costs, ACM Transactions on Algorithms 6(2): (2010).

Digital Library

[30]

D. Tcha and B. Lee, A branch-and-bound algorithm for the multilevel uncapacitated facility location problem. European J. Oper. Res. 18 (1984), no. 1, 3543.

[31]

T. Van Roy and D. Erlenkotter, A dual based procedure for dynamic facility location, Management Science 28:1091--1105, 1982.

[32]

J. Zhang, Approximating the two-level facility location problem via a quasi-greedy approach. Math. Program. 108(1): 159--176 (2006).

Digital Library

Cited By

Wu CXu DZhang DZhang P(2018)Approximation algorithms for the robust/soft-capacitated 2-level facility location problemsJournal of Global Optimization10.1007/s10898-017-0566-170:1(207-222)Online publication date: 1-Jan-2018
https://dl.acm.org/doi/10.1007/s10898-017-0566-1
Kathuria TSudarshan SSallinger EVan den Bussche JGeerts F(2017)Efficient and Provable Multi-Query OptimizationProceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/3034786.3034792(53-67)Online publication date: 9-May-2017
https://dl.acm.org/doi/10.1145/3034786.3034792
Wu CDu DXu D(2015)Primal-dual approximation algorithm for the two-level facility location problem via a dual quasi-greedy approachTheoretical Computer Science10.1016/j.tcs.2014.09.045562:C(213-226)Online publication date: 11-Jan-2015
https://dl.acm.org/doi/10.1016/j.tcs.2014.09.045

Index Terms

Inapproximability of the multi-level uncapacitated facility location problem
1. Mathematics of computing
  1. Mathematical analysis
    1. Functional analysis
      1. Approximation
2. Theory of computation
  1. Computational complexity and cryptography
    1. Complexity classes
  2. Design and analysis of algorithms
    1. Approximation algorithms analysis

Recommendations

Inapproximability of the Multilevel Uncapacitated Facility Location Problem

In this article, we present improved inapproximability results for the k-level uncapacitated facility location problem. In particular, we show that there is no polynomial time approximation algorithm with performance guarantee better than 1.539 unless P ...
Improved Approximation Algorithms for the Uncapacitated Facility Location Problem

We consider the uncapacitated facility location problem. In this problem, there is a set of locations at which facilities can be built; a fixed cost f_i is incurred if a facility is opened at location i. Furthermore, there is a set of demand locations ...
Improved Approximation Algorithm for k-level Uncapacitated Facility Location Problem (with Penalties)

We study the k-level uncapacitated facility location problem (k-level UFL) in which clients need to be connected with paths crossing open facilities of k types (levels). In this paper we first propose an approximation algorithm that for any constant k, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

SODA '12: Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete algorithms

January 2012

1764 pages

Sponsors

Kyoto University: Kyoto University

In-Cooperation

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 17 January 2012

Check for updates

Qualifiers

Research-article

Conference

SODA '12

Sponsor:

Kyoto University

SODA '12: ACM-SIAM Symposium on Discrete Algorithms

January 17 - 19, 2012

Kyoto, Japan

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
167
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wu CXu DZhang DZhang P(2018)Approximation algorithms for the robust/soft-capacitated 2-level facility location problemsJournal of Global Optimization10.1007/s10898-017-0566-170:1(207-222)Online publication date: 1-Jan-2018
https://dl.acm.org/doi/10.1007/s10898-017-0566-1
Kathuria TSudarshan SSallinger EVan den Bussche JGeerts F(2017)Efficient and Provable Multi-Query OptimizationProceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/3034786.3034792(53-67)Online publication date: 9-May-2017
https://dl.acm.org/doi/10.1145/3034786.3034792
Wu CDu DXu D(2015)Primal-dual approximation algorithm for the two-level facility location problem via a dual quasi-greedy approachTheoretical Computer Science10.1016/j.tcs.2014.09.045562:C(213-226)Online publication date: 11-Jan-2015
https://dl.acm.org/doi/10.1016/j.tcs.2014.09.045

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 Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents