Semidefinite and Linear Programming Integrality Gaps for Scheduling Identical Machines

Sherali-Adams [25] and Lovasz-Schrijver [21] developed systematic procedures to strengthen a relaxation known as lift-and-project methods. They have been proven to be a strong tool for developing approximation algorithms, matching the best relaxations known for problems like Max-Cut and Sparsest-Cut. In this work we provide lower bounds for these hierarchies when applied over the configuration LP for the problem of scheduling identical machines to minimize the makespan. First we show that the configuration LP has an integrality gap of at least 1024/1023 by providing a family of instances with 15 different job sizes. Then we show that for any integer n there is an instance with n jobs in this family such that after Omega(n) rounds of the Sherali-Adams (SA) or the Lovasz-Schrijver (LS+) hierarchy the integrality gap remains at least 1024/1023.