nach oben

Erschienen in:

2017 | OriginalPaper | Buchkapitel

Recent Developments in Approximation Algorithms for Facility Location and Clustering Problems

verfasst von : Hyung-Chan An, Ola Svensson

Erschienen in: Combinatorial Optimization and Graph Algorithms

Verlag: Springer Singapore

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We survey approximation algorithms for facility location and clustering problems, focusing on the recent developments. In particular, we review two algorithmic methodologies that have successfully lead to the current best approximation guarantees known: local search and linear programming based methods.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Nächstes Kapitel Graph Stabilization: A Survey

This factor was improved to \((5+\varepsilon )\) in the journal version [31] of the same paper.

This choice of constant must be large enough to offset the choice of 9 in the lemma’s statement.

We have that the opening cost of \(\bar{S}\) is greater than a constant fraction of the opening cost of S; moreover, this inequality has a small slack that is proportional to the per facility connection cost of \(\bar{S}\).

This, of course, is true only for those clients that are near i, the center of the ball.

The comparison has a slight error (see Note 4), which is charged against the slack described in Note 3. This balancing, along with the choice of constant in Note 2, determines the overall approximation ratio of 9.

We remark that the conference version of this paper claimed a guarantee of \(2.611+\varepsilon \) where the additional improvement came from an improved Lagrangian multiplier preserving algorithm for facility location. The up-to-date arXiv version of the same paper [11] however noted that this part of their improvement unfortunately contained an error, changing the final approximation guarantee to \(2.675+\varepsilon \).

Z. Abrams, A. Meyerson, K. Munagala, S. Plotkin, On the integrality gap of capacitated facility location. Technical Report CMU-CS-02-199 (Carnegie Mellon University, 2002), http://theory.stanford.edu/~za/CapFL/CapFL.pdf

A. Aggarwal, A. Louis, M. Bansal, N. Garg, N. Gupta, S. Gupta, S. Jain, A 3-approximation algorithm for the facility location problem with uniform capacities. Math. Progr. 141(1–2), 527–547 (2013)MathSciNetCrossRefMATH

S. Ahmadian, A. Norouzi-Fard, O. Svensson, J. Ward, Better guarantees for k-means and euclidean k-median by primal-dual algorithms (2016), http://arxiv.org/abs/1612.07925. CoRR abs/1612.07925

H.C. An, A. Bhaskara, C. Chekuri, S. Gupta, V. Madan, O. Svensson, Centrality of trees for capacitated \(k\)-center. Math. Progr. 154(1), 29–53 (2015). doi:10.1007/s10107-014-0857-y

H.C, An, M. Singh, O. Svensson, LP-based algorithms for capacitated facility location, in Proceedings of the 55th Annual Symposium on Foundations of Computer Science (FOCS) (2014), pp. 256–265

V. Arya, N. Garg, R. Khandekar, A. Meyerson, K. Munagala, V. Pandit, Local search heuristic for k-median and facility location problems, in Proceedings of the Thirty-third Annual ACM Symposium on Theory of Computing, STOC 2001, pp. 21–29. doi:10.1145/380752.380755

M.L. Balinski, On finding integer solutions to linear programs, in Proceedings of the IBM Scientific Computing Symposium on Combinatorial Problems (1966), pp. 225–248

M. Bansal, N. Garg, N. Gupta, A 5-approximation for capacitated facility location, in Proceedings of the 20th European Symposium on Algorithms (ESA) (2012), pp. 133–144

J. Byrka, An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem, in APPROX-RANDOM (2007), pp. 29–43

10.

J. Byrka, K. Fleszar, B. Rybicki, J. Spoerhase, Bi-factor approximation algorithms for hard capacitated k-median problems, in Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, pp. 722–736, http://dl.acm.org/citation.cfm?id=2722129.2722178

11.

J. Byrka, T. Pensyl, B. Rybicki, A. Srinivasan, K. Trinh, An improved approximation for \(k\)-median, and positive correlation in budgeted optimization (2014), http://arxiv.org/abs/1406.2951. CoRR abs/1406.2951

12.

J. Byrka, T. Pensyl, B. Rybicki, A. Srinivasan, K. Trinh, An improved approximation for \(k\)-median, and positive correlation in budgeted optimization, in Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, pp. 737–756, http://dl.acm.org/citation.cfm?id=2722129.2722179

13.

R.D. Carr, L.K. Fleischer, V.J. Leung, C.A. Phillips, Strengthening integrality gaps for capacitated network design and covering problems, in Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (2000), pp. 106–115

14.

M. Charikar, S. Guha, Improved combinatorial algorithms for facility location problems. SIAM J. Comput. 34(4), 803–824 (2005)MathSciNetCrossRefMATH

15.

M. Charikar, S. Guha, E. Tardos, D.B. Shmoys, A constant-factor approximation algorithm for the k-median problem (extended abstract), in Proceedings of the Thirty-first Annual ACM Symposium on Theory of Computing, STOC 1999, pp. 1–10. doi:10.1145/301250.301257

16.

M. Charikar, S. Li, A Dependent LP-Rounding Approach for the k-Median Problem in 39th International Colloquium on Automata, Languages, and Programming, ICALP 2012, pp. 194–205. doi:10.1007/978-3-642-31594-7_17

17.

F.A. Chudak, D.B. Shmoys, Improved approximation algorithms for the uncapacitated facility location problem. SIAM J. Comput. 33(1), 1–25 (2004)MathSciNetCrossRefMATH

18.

F.A. Chudak, D.P. Williamson, Improved approximation algorithms for capacitated facility location problems. Math. Progr. 102(2), 207–222 (2005)MathSciNetCrossRefMATH

19.

V. Cohen-Addad, P.N. Klein, C. Mathieu, Local search yields approximation schemes for \(k\)-means and \(k\)-median in euclidean and minor-free metrics, in Proceedings of the 57nd Annual Symposium on Foundations of Computer Science (FOCS) (2016), pp. 353–364

20.

M. Cygan, M. Hajiaghayi, S. Khuller, LP rounding for k-centers with non-uniform hard capacities, in FOCS (2012), pp. 273–282

21.

H.G. Demirci, S. Li, Constant approximation for capacitated k-median with (1+eps.)-capacity violation, in 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016 (2016), pp. 73:1–73:14

22.

G. Diehr, An algorithm for the \(p\)-median problem. Technical Report No. 191 (Western Management Science Institute, UCLA 1972)

23.

Z. Friggstad, M. Rezapour, M. Salavatipour, Local search yields a PTAS for \(k\)-means in doubling metrics, in Proceedings of the 57nd Annual Symposium on Foundations of Computer Science (FOCS) (2016), pp. 365-374

24.

S. Guha, S. Khuller, Greedy strikes back: Improved facility location algorithms. J. Algorithms 31(1), 228–248 (1999)MathSciNetCrossRefMATH

25.

D.S. Hochbaum, D.B. Shmoys, A best possible heuristic for the \(k\)-center problem. Math. Oper. Res. 10, 180–184 (1985)MathSciNetCrossRefMATH

26.

W.L. Hsu, G.L. Nemhauser, Easy and hard bottleneck location problems. Discret. Appl. Math. 1(3), 209–215 (1979). doi:10.1016/0166-218X(79)90044-1, http://www.sciencedirect.com/science/article/pii/0166218X79900441

27.

K. Jain, M. Mahdian, A. Saberi, A new greedy approach for facility location problems, in Proceedings of the 34th annual ACM symposium on Theory of computing (STOC) (2002), pp. 731–740

28.

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

29.

T. Kanungo, D.M. Mount, N.S. Netanyahu, C.D. Piatko, R. Silverman, A.Y. Wu, An efficient k-means clustering algorithm: analysis and implementation. IEEE Trans. Pattern Anal. Mach. Intell. 24(7), 881–892 (2002). doi:10.1109/TPAMI.2002.1017616

30.

M.R. Korupolu, C.G. Plaxton, R. Rajaraman, Analysis of a local search heuristic for facility location problems, in Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1998, pp. 1–10, http://dl.acm.org/citation.cfm?id=314613.314616

31.

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

32.

A.A. Kuehn, M.J. Hamburger, A heuristic program for locating warehouses. Manag. Sci. 9(4), 643–666 (1963)CrossRef

33.

E. Lee, M. Schmidt, J. Wright, Improved and simplified inapproximability for k-means (2015), arXiv:1509.00916

34.

S. Li, A 1.488 approximation algorithm for the uncapacitated facility location problem. Inf. Comput. 222(0), 45–58 (2013). doi:10.1016/j.ic.2012.01.007, http://www.sciencedirect.com/science/article/pii/S0890540112001459

35.

S. Li, Approximating capacitated \(k\)-median with \((1+\epsilon )k\) open facilities, in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, pp. 786–796, http://dl.acm.org/citation.cfm?id=2884435.2884491

36.

S. Li, O. Svensson, Approximating k-median via pseudo-approximation, in Proceedings of the Forty-fifth Annual ACM Symposium on Theory of Computing, STOC 2013, pp. 901–910. doi:10.1145/2488608.2488723

37.

A.S. Manne, Plant location under economies-of-scale-decentralization and computation. Manage. Sci. 11(2), 213–235 (1964). doi:10.1287/mnsc.11.2.213

38.

M. Pál, É. Tardos, T. Wexler, Facility location with nonuniform hard capacities, in Proceedings of the 42nd Annual Symposium on Foundations of Computer Science (FOCS) (2001), pp. 329–338

39.

D.B. Shmoys, E. Tardos, K. Aardal, Approximation algorithms for facility location problems (extended abstract), in Proceedings of the 29th annual ACM symposium on Theory of computing (STOC) (1997), pp. 265–274

40.

J.F. Stollsteimer, A working model for plant numbers and locations. J. Farm Econ. 45(3), 631–645 (1963), http://www.jstor.org/stable/1235442

41.

M.B. Teitz, P. Bart, Heuristic methods for estimating the generalized vertex median of a weighted graph. Oper. Res. 16(5), 955–961 (1968). doi:10.1287/opre.16.5.955 CrossRefMATH

42.

L.A. Wolsey, Faces for a linear inequality in 0–1 variables. Math. Progr. 8(1), 165–178 (1975). doi:10.1007/BF01580441

Titel: Recent Developments in Approximation Algorithms for Facility Location and Clustering Problems
verfasst von: Hyung-Chan An
Ola Svensson
Verlag: Springer Singapore
Buch: Combinatorial Optimization and Graph Algorithms
Print ISBN: 978-981-10-6146-2

Electronic ISBN: 978-981-10-6147-9

Copyright-Jahr: 2017
DOI: https://doi.org/10.1007/978-981-10-6147-9_1

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"