On the configuration-LP for schesduling on unrelated machines

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].