On the configuration-LP for scheduling on unrelated machines.

Abstract

Closing the approximability gap between 3/2and 2 for the minimum makespan problem on unrelatedmachines is one of the most important open questions inscheduling. Almost all known approximation algorithms forthe problem are based on linear programs (LPs). In this paper,we identify a surprisingly simple class of instances whichconstitute the core difficulty for LPs: the so far hardly studiedunrelated graph balancing case in which each job can beassigned to at most two machines. We prove that already forthis basic setting the strongest LP-relaxation studied so far—the configuration-LP—has an integrality gap of 2, matchingthe 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 loadin the unrelated graph balancing setting, we present an elegantpurely combinatorial 2-approximation algorithm withonly quadratic running time. Our algorithm uses a novel preprocessingroutine that estimates the optimal value as good asthe configuration-LP. This improves on the computationallycostly LP-based algorithm by Chakrabarty et al. (Proceedingsof the 50th Annual Symposium on Foundations of ComputerScience (FOCS 2009), pp 107–116, 2009) that achieves thesame approximation guarantee.