Skip to main content
main-content

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

01.08.2014 | Ausgabe 4/2014

Journal of Scheduling 4/2014

On the configuration-LP for scheduling on unrelated machines

Zeitschrift:
Journal of Scheduling > Ausgabe 4/2014
Autoren:
José Verschae, Andreas Wiese

Abstract

Closing the approximability gap between \(3/2\) and 2 for the minimum makespan problem on unrelated machines is one of the most important open questions in scheduling. Almost all known approximation algorithms for the problem are based on linear programs (LPs). In this paper, we identify a surprisingly simple class of instances which constitute the core difficulty for LPs: the so far hardly studied unrelated graph balancing case in which each job can be assigned to at most two machines. We prove that already for this basic setting the strongest LP-relaxation studied so far—the configuration-LP—has an integrality gap of 2, matching the best known approximation factor for the general case. This points toward an interesting direction of future research. For the objective of maximizing the minimum machine load in the unrelated graph balancing setting, we present an elegant purely combinatorial 2-approximation algorithm with only quadratic running time. Our algorithm uses a novel preprocessing routine that estimates the optimal value as good as the configuration-LP. This improves on the computationally costly LP-based algorithm by Chakrabarty et al. (Proceedings of the 50th Annual Symposium on Foundations of Computer Science (FOCS 2009), pp 107–116, 2009) that achieves the same approximation guarantee.

Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten

Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit dem Kombi-Abo erhalten Sie vollen Zugriff auf über 1,8 Mio. Dokumente aus mehr als 61.000 Fachbüchern und rund 500 Fachzeitschriften aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Umwelt
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe

Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Wirtschaft"

Online-Abonnement

Mit dem Wirtschafts-Abo erhalten Sie Zugriff auf über 1 Mio. Dokumente aus mehr als 45.000 Fachbüchern und 300 Fachzeitschriften aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb

Testen Sie jetzt 30 Tage kostenlos.

Literatur
Über diesen Artikel

Weitere Artikel der Ausgabe 4/2014

Journal of Scheduling 4/2014 Zur Ausgabe

Premium Partner

BranchenIndex Online

Die B2B-Firmensuche für Industrie und Wirtschaft: Kostenfrei in Firmenprofilen nach Lieferanten, Herstellern, Dienstleistern und Händlern recherchieren.

Whitepaper

- ANZEIGE -

Wie können Sie Stress im Fernstudium bewältigen?

Ein Fernstudium erfordert ein hohes Maß an Selbstorganisation und Disziplin. Das bedeutet oft Stress - Prüfungsstress, Abgabetermine, Zeitdruck… Stress wird dann zum Problem, wenn wir ihn nicht mehr im Griff haben. Wenn wir die Ursachen und auch Auswirkungen von Stress verstehen, ist das ein wichtiger Schritt hin zu einem erfolgreichen Stressmanagement. Lesen Sie in diesem Auszug aus dem Fachbuch "Stressmanagement im Fernstudium" wie Sie Ihren Stress effektiv bewältigen können. Inklusive Selbsttest.
Jetzt gratis downloaden!

Bildnachweise