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
Journal of Combinatorial Optimization
Erschienen in: Journal of Combinatorial Optimization 1/2015

01.01.2015

Improved local search for universal facility location

verfasst von: Eric Angel, Nguyen Kim Thang, Damien Regnault

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 1/2015

Einloggen

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

search-config
loading …

Abstract

We consider the universal facility location problem in which the goal is to assign clients to facilities in order to minimize the sum of connection and facility costs. The connection cost is proportional to the distance each client has to travel to its assigned facility, whereas the cost of a facility is a non-decreasing function depending on the number of clients assigned to the facility. This model generalizes several variants of facility location problems. We present a \((5.83 + \epsilon )\) approximation algorithm for this problem based on local search technique.
Vorheriger Artikel Online unbounded batch scheduling on parallel machines with delivery times
Nächster Artikel Tractable connected domination for restricted bipartite graphs

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 "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

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
Literatur
Aggarwal A, Louis A, Bansal M, Garg N, Gupta N, Gupta S, and Jain S (2010) A 3-approximation for facility location with uniform capacities. In: Proceedings 14th conference on integer programming and combinatorial cptimization (IPCO), pp 149–162
Arya V, Garg N, Khandekar R, Meyerson A, Munagala K, Pandit V (2004) Local search heuristics for \(k\)-median and facility location problems. SIAM J Comput 33(3):544–562CrossRefMATHMathSciNet
Bansal M, Garg N, Gupta N (2012) A 5-approximation for capacitated facility location. In: Proceedings 20th European symposium on algorithms (ESA), pp 133–144
Garg N, Khandekar R, Pandit V (2005) Improved approximation for universal facility location. In: Proceedings 16th symposium on discrete algorithms, pp 959–960
Hajiaghayi MT, Mahdian M, Mirrokni VS (2003) The facility location problem with general cost functions. Networks 42(1):42–47CrossRefMATHMathSciNet
Li J, Khuller S (2011) Generalized machine activation problems. In: Proceedings of the twenty-second Annual ACM-SIAM symposium on discrete algorithms (SODA), pp 80–94
Mahdian M, Pál M (2003) Universal facility location. In: Proceedings 11th Annual European symposium on algorithms (ESA), pp 409–421
Pál M, Tardos É, Wexler T (2001) Facility location with nonuniform hard capacities. In: Proceedings 42nd annual symposium on foundations of computer science, pp 329–338
Zhang J, Chen B, Ye Y (2005) A multiexchange local search algorithm for the capacitated facility location problem. Math Oper Res 30(2):389–403CrossRefMATHMathSciNet
Metadaten
Titel
Improved local search for universal facility location
verfasst von
Eric Angel
Nguyen Kim Thang
Damien Regnault
Publikationsdatum
01.01.2015
Verlag
Springer US
Erschienen in
Journal of Combinatorial Optimization / Ausgabe 1/2015
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI
https://doi.org/10.1007/s10878-014-9711-7

Weitere Artikel der Ausgabe 1/2015

Journal of Combinatorial Optimization 1/2015 Zur Ausgabe

OriginalPaper

New bounds for the balloon popping problem

OriginalPaper

Tractable connected domination for restricted bipartite graphs

OriginalPaper

Covering tree with stars

OriginalPaper

An effective branching strategy based on structural relationship among multiple forbidden induced subgraphs

OriginalPaper

Online unbounded batch scheduling on parallel machines with delivery times

OriginalPaper

Improved approximation algorithms for computing disjoint paths subject to two constraints