Paper Info
Title
Semidefinite and Linear Programming Integrality Gaps for Scheduling Identical Machines.
Abstract
Sherali-Adams [25] and Lovász-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\\text {/}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 $$\\varOmega n$$ rounds of the Sherali-Adams $$\\text {SA}$$ or the Lovász-Schrijver $$\\text {LS}_+$$ hierarchy the integrality gap remains at least $$1024\\text {/}1023$$.
Year
DOI
Venue
2018
10.1007/978-3-319-33461-5_13
IPCO
Keywords
DocType
Volume
Identical machine scheduling,Configuration LP,Sherali–Adams,Lovász–Schrijver,68W25,90C05,90C22
Journal
172
Issue
ISSN
Citations 
1-2
0302-9743
0
PageRank 
References 
Authors
0.34
19
6
Name
Order
Citations
PageRank
Adam Kurpisz1363.38
Monaldo Mastrolilli251439.27
Claire Mathieu345225.78
Tobias Mömke419317.86
Víctor Verdugo5125.03
Andreas Wiese67110.71