Abstract

Closing the approximability gap between 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.