On the configuration-LP for schesduling on unrelated machines

José Verschae, Andreas Wiese

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

13 Scopus citations


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 known LP-formulation - the configuration-LP - has an integrality gap of 2, matching the best known approximation factor for the general case. This points towards an interesting direction of future research. The result is shown by a sophisticated construction of instances, based on deep insights on two key weaknesses of the configuration-LP. 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 (2+ε)-approximation algorithm by Chakrabarty et al. [6].

Original languageEnglish
Title of host publicationAlgorithms, ESA 2011 - 19th Annual European Symposium, Proceedings
Number of pages13
StatePublished - 2011
Externally publishedYes
Event19th Annual European Symposium on Algorithms, ESA 2011 - Saarbrucken, Germany
Duration: 5 Sep 20119 Sep 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6942 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference19th Annual European Symposium on Algorithms, ESA 2011


Dive into the research topics of 'On the configuration-LP for schesduling on unrelated machines'. Together they form a unique fingerprint.

Cite this