On the extension complexity of scheduling

Abstract

We study the minimum makespan problem on identical machines in which we want to assign a set of n given jobs to m machines in order to minimize the maximum load over the machines. We prove upper and lower bounds for the extension complexity of its linear programming formulations. In particular, we prove that the canonical formulation for the problem has extension complexity 2(Omega(n/logn)), even if each job has size 1 or 2 and the optimal makespan is 2.