Abstract: Sherali and Adams (SIAM J Discrete Math 3:411–430, 1990) and Lovasz and Schrijver (SIAM J Optim 1:166–190, 1991) developed systematic procedures to construct the hierarchies of relaxations 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 ...
(read more)
Topics: 
Combinatorics
Discrete mathematics
Mathematical optimization