Skip to main content
Erschienen in: Journal of Combinatorial Optimization 1/2014

01.01.2014

Online bottleneck matching

verfasst von: Barbara M. Anthony, Christine Chung

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

Einloggen

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

search-config
loading …

Abstract

We consider the online bottleneck matching problem, where \(k\) server-vertices lie in a metric space and \(k\) request-vertices that arrive over time each must immediately be permanently assigned to a server-vertex. The goal is to minimize the maximum distance between any request and its server. Because no algorithm can have a competitive ratio better than \(O(k)\) for this problem, we use resource augmentation analysis to examine the performance of three algorithms: the naive Greedy algorithm, Permutation, and Balance. We show that while the competitive ratio of Greedy improves from exponential (when each server-vertex has one server) to linear (when each server-vertex has two servers), the competitive ratio of Permutation remains linear when an extra server is introduced at each server-vertex. The competitive ratio of Balance is also linear with an extra server at each server-vertex, even though it has been shown that an extra server makes it constant-competitive for the min-weight matching 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!

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!

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!

Literatur
Zurück zum Zitat Chung C, Pruhs K, Uthaisombut P (2008) The online transportation problem: on the exponential boost of one extra server. In: LATIN 2008, pp 228–239 Chung C, Pruhs K, Uthaisombut P (2008) The online transportation problem: on the exponential boost of one extra server. In: LATIN 2008, pp 228–239
Zurück zum Zitat Hartline JD, Roughgarden T (2009) Simple versus optimal mechanisms. In: ACM conference on electronic commerce, pp 225–234 Hartline JD, Roughgarden T (2009) Simple versus optimal mechanisms. In: ACM conference on electronic commerce, pp 225–234
Zurück zum Zitat Idury R, Schaffer A (1992) A better lower bound for on-line bottleneck matching, manuscript Idury R, Schaffer A (1992) A better lower bound for on-line bottleneck matching, manuscript
Zurück zum Zitat Kalyanasundaram B, Pruhs K (1993) Online weighted matching. J Algorithms 14(3):478–488. Preliminary version appeared in SODA, pp 231–240, 1991 Kalyanasundaram B, Pruhs K (1993) Online weighted matching. J Algorithms 14(3):478–488. Preliminary version appeared in SODA, pp 231–240, 1991
Zurück zum Zitat Kalyanasundaram B, Pruhs K (2000b) The online transportation problem. SIAM J Discrete Math 13(3): 370–383. Preliminary version appeared in ESA, pp 484–493, 1995 Kalyanasundaram B, Pruhs K (2000b) The online transportation problem. SIAM J Discrete Math 13(3): 370–383. Preliminary version appeared in ESA, pp 484–493, 1995
Zurück zum Zitat Phillips CA, Stein C, Torng E, Wein J (2002) Optimal time-critical scheduling via resource augmentation. Algorithmica 32(2):163–200. Preliminary version appeared in STOC, pp 140–149, 1997 Phillips CA, Stein C, Torng E, Wein J (2002) Optimal time-critical scheduling via resource augmentation. Algorithmica 32(2):163–200. Preliminary version appeared in STOC, pp 140–149, 1997
Zurück zum Zitat Roughgarden T, Tardos É (2002) How bad is selfish routing? J ACM 49(2):236–259. Preliminary version appeared in FOCS, pp 93–102, 2000 Roughgarden T, Tardos É (2002) How bad is selfish routing? J ACM 49(2):236–259. Preliminary version appeared in FOCS, pp 93–102, 2000
Metadaten
Titel
Online bottleneck matching
verfasst von
Barbara M. Anthony
Christine Chung
Publikationsdatum
01.01.2014
Verlag
Springer US
Erschienen in
Journal of Combinatorial Optimization / Ausgabe 1/2014
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI
https://doi.org/10.1007/s10878-012-9581-9

Weitere Artikel der Ausgabe 1/2014

Journal of Combinatorial Optimization 1/2014 Zur Ausgabe

EditorialNotes

Preface