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 the Capture Time of Cops and Robbers Game on a Planar Graph Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

An Approximation Algorithm for the k-Median Problem with Uniform Penalties via Pseudo-Solutions

verfasst von : Chenchen Wu, Donglei Du, Dachuan Xu

Erschienen in: Combinatorial Optimization and Applications

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

We present a \((1+ \sqrt{3} + \epsilon )\)-approximation algorithm for the k-median problem with uniform penalties in polynomial time, extending the recent result by Li and Svensson for the classical k-median problem without penalties. One important difference of this work from that of Li and Svensson is a new definition of sparse instance to exploit the combinatorial structure of our problem.

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 Optimal Speed Scaling with a Solar Cell
Nächstes Kapitel On-Line Pattern Matching on Uncertain Sequences and Applications
Literatur
1.
Arya, V., Garg, N., Khandekar, R., Meyerson, A., Munagala, K., Pandit, V.: Local search heuristics for \(k\)-median and facility location problems. SIAM J. Comput. 33, 544–562 (2004)MathSciNetCrossRefMATH
2.
Charikar, M., Guha, S., Tardos, E., Shmoys, D.B.: A constant-factor approximation algorithm for the \( k\)-median problem. J. Comput. Syst. Sci. 65, 129–149 (2002)MathSciNetCrossRefMATH
3.
Charikar M., Khuller S., Mount, D.M., Narasimhan, G.: Algorithms for facility location problems with outliers. In: Proceedings of SODA, pp. 642–651 (2001)
4.
Chudak, F.A., Shmoys, D.B.: Improved approximation algorithms for the uncapacitated facility location problem. SIAM J. Comput. 33, 1–25 (2003)MathSciNetCrossRefMATH
5.
Guha, S., Khuller, S.: Greedy strikes back: improved facility location algorithms. In: Proceedings of SODA, pp. 649–657 (1998)
6.
Hajiaghayi, M., Khandekar, R., Kortsarz, G.: Local search algorithms for the red-blue median problem. Algorithmica 63, 795–814 (2012)MathSciNetCrossRefMATH
7.
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)MathSciNetCrossRefMATH
8.
Jain, K., Mahdian, M., Saberi, A.: A new greedy approach for facility location problems. In: Proceedings of STOC, pp. 731–740 (2002)
9.
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)MathSciNetCrossRefMATH
10.
Li, S., Svensson, O.: Approximating \(k\)-median via pseudo-approximation. In: Procedings of STOC, pp. 901–910 (2013)
11.
Li, Y., Du, D., Xiu, N., Xu, D.: Improved approximation algorithms for the facility location problems with linear/submodular penalties. Algorithmica 73, 460–482 (2015)MathSciNetCrossRefMATH
12.
13.
Wang, Y., Xu, D., Du, D., Wu, C.: Local search algorithms for \(k\)-median and \(k\)-facility location problems with linear penalties. In: Proceedings of COCOA, pp. 60–71 (2015)
14.
Shmoys, D.B., Tardos, E., Aardal, K.I.: Approximation algorithms for facility location problems. In: Proceedings of STOC, pp. 265–274 (1997)
Metadaten
Titel
An Approximation Algorithm for the k-Median Problem with Uniform Penalties via Pseudo-Solutions
verfasst von
Chenchen Wu
Donglei Du
Dachuan Xu
Copyright-Jahr
2016
Buch
Combinatorial Optimization and Applications

Print ISBN: 978-3-319-48748-9

Electronic ISBN: 978-3-319-48749-6

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-319-48749-6_39