Semidefinite and linear programming integrality gaps for scheduling identical machines

Adam Kurpisz; Monaldo Mastrolilli; Claire Mathieu; Tobias Mömke; Victor Verdugo; Andreas Wiese

doi:10.1007/s10107-017-1152-5

Semidefinite and linear programming integrality gaps for scheduling identical machines

Adam Kurpisz, Monaldo Mastrolilli, Claire Mathieu, Tobias Mömke, Victor Verdugo, Andreas Wiese

Operations Analytics

Research output: Contribution to Journal › Article › Academic › peer-review

Abstract

Sherali and Adams (SIAM J Discrete Math 3:411–430, 1990) and Lovász 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 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 Ω(n) rounds of the Sherali–Adams (SA) or the Lovász–Schrijver (LS+) hierarchy the integrality gap remains at least 1024/1023.

Original language	English
Pages (from-to)	231-248
Number of pages	18
Journal	Math. Program.
Volume	172
Issue number	1-2
Early online date	10 May 2017
DOIs	https://doi.org/10.1007/s10107-017-1152-5
Publication status	Published - Nov 2018

Funding

Supported by the Swiss National Science Foundation project 200020-144491/1 “Approximation Algorithms for Machine Scheduling Through Theory and Experiments,” by Sciex Project 12.311, by DFG Grant MO 2889/1-1, and by CONICYT-PCHA/Doctorado Nacional/2014-21140930. Supported by the Swiss National Science Foundation project 200020-144491/1 ?Approximation Algorithms for Machine Scheduling Through Theory and Experiments,? by Sciex Project 12.311, by DFG Grant MO 2889/1-1, and by CONICYT-PCHA/Doctorado Nacional/2014-21140930.

Funders	Funder number
CONICYT-PCHA/Doctorado	Nacional/2014-21140930
California Department of Fish and Game
Deutsche Forschungsgemeinschaft	MO 2889/1-1
Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschung	12.311, 200020-144491/1

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

Access to Document

10.1007/s10107-017-1152-5

Persistent URL (handle)

Persistent link

Cite this

@article{a9961b1f66e7416f8719299f4224d976,

title = "Semidefinite and linear programming integrality gaps for scheduling identical machines",

abstract = "Sherali and Adams (SIAM J Discrete Math 3:411–430, 1990) and Lov{\'a}sz 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 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 Ω(n) rounds of the Sherali–Adams (SA) or the Lov{\'a}sz–Schrijver (LS+) hierarchy the integrality gap remains at least 1024/1023.",

author = "Adam Kurpisz and Monaldo Mastrolilli and Claire Mathieu and Tobias M{\"o}mke and Victor Verdugo and Andreas Wiese",

year = "2018",

month = nov,

doi = "10.1007/s10107-017-1152-5",

language = "English",

volume = "172",

pages = "231--248",

journal = "Math. Program.",

issn = "1436-4646",

publisher = "Springer-Verlag GmbH and Co. KG",

number = "1-2",

}

TY - JOUR

T1 - Semidefinite and linear programming integrality gaps for scheduling identical machines

AU - Kurpisz, Adam

AU - Mastrolilli, Monaldo

AU - Mathieu, Claire

AU - Mömke, Tobias

AU - Verdugo, Victor

AU - Wiese, Andreas

PY - 2018/11

Y1 - 2018/11

N2 - Sherali and Adams (SIAM J Discrete Math 3:411–430, 1990) and Lovász 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 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 Ω(n) rounds of the Sherali–Adams (SA) or the Lovász–Schrijver (LS+) hierarchy the integrality gap remains at least 1024/1023.

AB - Sherali and Adams (SIAM J Discrete Math 3:411–430, 1990) and Lovász 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 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 Ω(n) rounds of the Sherali–Adams (SA) or the Lovász–Schrijver (LS+) hierarchy the integrality gap remains at least 1024/1023.

U2 - 10.1007/s10107-017-1152-5

DO - 10.1007/s10107-017-1152-5

M3 - Article

SN - 1436-4646

VL - 172

SP - 231

EP - 248

JO - Math. Program.

JF - Math. Program.

IS - 1-2

ER -

Semidefinite and linear programming integrality gaps for scheduling identical machines

Abstract

Funding

UN SDGs

Access to Document

Persistent URL (handle)

Fingerprint

Cite this