Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
On a Reformulation of Mathematical Programs with Cardinality Constraints Kapitel lesen Erstes Kapitel lesen

2015 | OriginalPaper | Buchkapitel

Approximation Algorithms for the Robust Facility Location Problem with Penalties

verfasst von : Fengmin Wang, Dachuan Xu, Chenchen Wu

Erschienen in: Advances in Global Optimization

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

In this paper, we consider the robust facility location problem with penalties, aiming to serve only a specified fraction of the clients. We formulate this problem as an integer linear programming to identify which clients must be served. Based on the corresponding LP relaxation and dual program, we propose a primal-dual 3-approximation algorithm. Combining the greedy augmentation procedure, we further improve the above approximation ratio to 2.

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
Vorheriges Kapitel A Survey on Approximation Mechanism Design Without Money for Facility Games
Nächstes Kapitel A Discrete State Transition Algorithm for Generalized Traveling Salesman Problem
Literatur
1.
Cornuejols, G., Nemhauser, G.L., Wolsey, L.A.: The uncapacitated facility location problem. In: Mirchandani, P.B., Francis, R.L. (eds.) Discrete Location Theory, pp. 119–171. Wiley, New York (1990)
2.
Kuehn, A.A., Hamburger, M.J.: A heuristic program for locating warehouses. Manag. Sci. 9, 643–666 (1963)CrossRef
3.
Charikar, M., Guha, S.: Improved combinatorial algorithms for facility location problems. SIAM J. Comput. 34, 803–824 (2005).CrossRefMATHMathSciNet
4.
Chudak, F.A., Shmoys, D.B.: Improved approximation algorithms for the uncapacitated facility location problem. SIAM J. Comput. 33, 1–25 ( 2003)CrossRefMATHMathSciNet
5.
6.
Jain, K., Mahdian, M., Markakis, E., Saberi, A., Vazirani, V.V.: Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP. J. ACM 50, 795–824 (2003)CrossRefMathSciNet
7.
Jain, K., Vazirani, V.V.: Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation. J. ACM 48, 274–296 (2001)CrossRefMATHMathSciNet
8.
Li, S.: A 1. 488-approximation algorithm for the uncapacitated facility location problem. In: Proceedings of ICALP, Part II, pp. 77–88 (2011)
9.
Mahdian, M., Ye, Y., Zhang, J.: Improved approximation algorithms for metric facility location problems. In: Proceedings of APPROX, pp. 229–242 (2002)
10.
Shmoys, D.B., Tardös, E., Aardal, K.I.: Approximation algorithms for facility location problems. In: Proceedings of STOC, pp. 265–274 (1997)
11.
Sviridenko, M.: An improved approximation algorithm for the metric uncapacitated facility location problem. In: Proceedings of IPCO, pp. 240–257 (2002)
12.
Ageev, A., Ye, Y., Zhang, J.: Improved combinatorial approximation algorithms for the k-level facility location problem. SIAM J. Discrete Math. 18, 207–217 (2003)CrossRefMathSciNet
13.
Chen, X., Chen, B.: Approximation algorithms for soft-capacitated facility location in capacitated network design. Algorithmica 53, 263–297 (2007)CrossRef
14.
Charikar, M., Khuller, S., Mount, D.M., Naraasimban, G.: Algorithms for facility location problems with outliers. In: Proceedings of SODA, pp. 642–651 (2001)
15.
Du, D., Lu, R., Xu, D.: A primal-dual approximation algorithm for the facility location problem with submodular penalties. Algorithmica 63, 191–200 (2012)CrossRefMATHMathSciNet
16.
Shu, J.: An efficient greedy heuristic for warehouse-retailer network design optimization. Transp. Sci. 44, 183–192 (2010)CrossRef
17.
Xu, G., Xu, J.: An LP rounding algorithm for approximating uncapacitated facility location problem with penalties. Inf. Process. Lett. 94, 119–123 (2005)CrossRefMATH
18.
Xu, G., Xu, J.: An improved approximation algorithm for uncapacitated facility location problem with penalties. J. Comb. Optim. 17, 424–436 (2008)CrossRef
19.
Ye, Y., Zhang, J.: An approximation algorithm for the dynamic facility location problem. In: Combinatorial Optimization in Communication Networks, pp. 623–637. Kluwer Academic, Dordrecht (2005)
20.
Zhang, J.: Approximating the two-level facility location problem via a quasi-greedy approach. Math. Program. 108, 159–176 (2006)CrossRefMATHMathSciNet
21.
Zhang, J., Chen, B., Ye, Y.: A multiexchange local search algorithm for the capacitated facility location problem. Math. Oper. Res. 30, 389–403 (2005)CrossRefMATHMathSciNet
22.
Zhang, P.: A new approximation algorithm for the k-facility location problem. Theor. Comput. Sci. 384, 126–135 (2007)CrossRefMATH
23.
Li, Y., Du, D., Xiu, N., Xu, D.: Improved approximation algorithms for the facility location problems with linear/submodular penalty. In: Proceedings of COCOON, pp. 292–303 (2013)
Metadaten
Titel
Approximation Algorithms for the Robust Facility Location Problem with Penalties
verfasst von
Fengmin Wang
Dachuan Xu
Chenchen Wu
Copyright-Jahr
2015
Buch
Advances in Global Optimization

Print ISBN: 978-3-319-08376-6

Electronic ISBN: 978-3-319-08377-3

Copyright-Jahr: 2015

DOI
https://doi.org/10.1007/978-3-319-08377-3_14