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:
Computing Equilibria with Partial Commitment Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

Bounds for the Convergence Time of Local Search in Scheduling Problems

verfasst von : Tobias Brunsch, Michael Etscheid, Heiko Röglin

Erschienen in: Web and Internet Economics

Verlag: Springer Berlin Heidelberg

Einloggen

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

search-config
loading …

Abstract

We study the convergence time of local search for a standard machine scheduling problem in which jobs are assigned to identical or related machines. Local search corresponds to the best response dynamics that arises when jobs selfishly try to minimize their costs. We assume that each machine runs a coordination mechanism that determines the order of execution of jobs assigned to it. We obtain various new polynomial and pseudo-polynomial bounds for the well-studied coordination mechanisms Makespan and Shortest-Job-First, using worst-case and smoothed analysis. We also introduce a natural coordination mechanism FIFO, which takes into account the order in which jobs arrive at a machine, and study both its impact on the convergence time and its price of anarchy.

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 FPT Approximation Schemes for Maximizing Submodular Functions
Nächstes Kapitel On the Price of Stability of Undirected Multicast Games
Literatur
1.
2.
3.
4.
Christodoulou, G., Koutsoupias, E., Nanavati, A.: Coordination mechanisms. In: Díaz, J., Karhumäki, J., Lepistö, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol. 3142, pp. 345–357. Springer, Heidelberg (2004). doi:10.​1007/​978-3-540-27836-8_​31 CrossRef
5.
Czumaj, A., Vöcking, B.: Tight bounds for worst-case equilibria. Trans. Algorithms ACM 3(1) (2007)
6.
Etscheid, M.: Performance guarantees for scheduling algorithms under perturbed machine speeds. In: Cai, L., Cheng, S.-W., Lam, T.-W. (eds.) ISAAC 2013. LNCS, vol. 8283, pp. 207–217. Springer, Heidelberg (2013). doi:10.​1007/​978-3-642-45030-3_​20 CrossRef
7.
Even-Dar, E., Kesselman, A., Mansour, Y.: Convergence time to Nash equilibria. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, pp. 502–513. Springer, Heidelberg (2003). doi:10.​1007/​3-540-45061-0_​41 CrossRef
8.
Feldmann, R., Gairing, M., Lücking, T., Monien, B., Rode, M.: Nashification and the coordination ratio for a selfish routing game. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, pp. 514–526. Springer, Heidelberg (2003). doi:10.​1007/​3-540-45061-0_​42 CrossRef
9.
10.
Garey, M.R., Johnson, D.S.: Complexity results for multiprocessor scheduling under resource constraints. SIAM J. Comput. 4, 397–411 (1975)MathSciNetCrossRefMATH
11.
Goldberg, P.W.: Bounds for the convergence rate of randomized local search in a multiplayer load-balancing game. In: Proceedings of the PODC 2004, pp. 131–140 (2004). doi:10.​1145/​1011767.​1011787
12.
Hurkens, C.A.J., Vredeveld, T.: Local search for multiprocessor scheduling: how many moves does it take to a local optimum? Oper. Res. Lett. 31(2), 137–141 (2003)MathSciNetCrossRefMATH
13.
14.
Manthey, B., Röglin, H.: Smoothed analysis: analysis of algorithms beyond worst case. IT - Information Technology 53(6), 280–286 (2011)CrossRef
15.
16.
Schuurman, P., Vredeveld, T.: Performance guarantees of local search for multiprocessor scheduling. Informs J. Comput. 19(1), 52–63 (2007)MathSciNetCrossRefMATH
17.
Spielman, D., Teng, S.-H.: Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time. J. ACM 51(3), 385–463 (2004)MathSciNetCrossRefMATH
18.
Spielman, D., Teng, S.-H.: Smoothed analysis: an attempt to explain the behavior of algorithms in practice. Commun. ACM 52(10), 76–84 (2009)CrossRef
Metadaten
Titel
Bounds for the Convergence Time of Local Search in Scheduling Problems
verfasst von
Tobias Brunsch
Michael Etscheid
Heiko Röglin
Copyright-Jahr
2016
Verlag
Springer Berlin Heidelberg
Buch
Web and Internet Economics

Print ISBN: 978-3-662-54109-8

Electronic ISBN: 978-3-662-54110-4

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-662-54110-4_24