On the extension complexity of scheduling polytopes

Hans Raj Tiwary; Victor Verdugo; Andreas Wiese

doi:10.1016/j.orl.2020.05.008

On the extension complexity of scheduling polytopes

Hans Raj Tiwary, Victor Verdugo, Andreas Wiese^*

^*Corresponding author for this work

Operations Analytics

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

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^Ω(n∕logn), even if each job has size 1 or 2 and the optimal makespan is 2.

Original language	English
Pages (from-to)	472-479
Number of pages	8
Journal	Operations Research Letters
Volume	48
Issue number	4
DOIs	https://doi.org/10.1016/j.orl.2020.05.008
Publication status	Published - Jul 2020

Bibliographical note

Funding Information:
Hans Raj Tiwary has been partially supported by the GAČR project, Czech Republic 17-09142S . Andreas Wiese has been partially supported by the grant Fondecyt Regular 1170223 .

Funding Information:
Hans Raj Tiwary has been partially supported by the GA?R project, Czech Republic17-09142S. Andreas Wiese has been partially supported by the grant Fondecyt Regular1170223.

Publisher Copyright:
© 2020 Elsevier B.V.

Keywords

Extended formulations
Linear programming
Makespan scheduling

UN SDGs

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

Access to Document

10.1016/j.orl.2020.05.008

Persistent URL (handle)

Copy link address

Cite this

@article{8db552f0548f444f9a2a2961a92f3372,

title = "On the extension complexity of scheduling polytopes",

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Ω(n∕logn), even if each job has size 1 or 2 and the optimal makespan is 2.",

keywords = "Extended formulations, Linear programming, Makespan scheduling",

author = "Tiwary, {Hans Raj} and Victor Verdugo and Andreas Wiese",

note = "Funding Information: Hans Raj Tiwary has been partially supported by the GA{\v C}R project, Czech Republic 17-09142S . Andreas Wiese has been partially supported by the grant Fondecyt Regular 1170223 . Funding Information: Hans Raj Tiwary has been partially supported by the GA?R project, Czech Republic17-09142S. Andreas Wiese has been partially supported by the grant Fondecyt Regular1170223. Publisher Copyright: {\textcopyright} 2020 Elsevier B.V.",

year = "2020",

month = jul,

doi = "10.1016/j.orl.2020.05.008",

language = "English",

volume = "48",

pages = "472--479",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier",

number = "4",

}

TY - JOUR

T1 - On the extension complexity of scheduling polytopes

AU - Tiwary, Hans Raj

AU - Verdugo, Victor

AU - Wiese, Andreas

N1 - Funding Information: Hans Raj Tiwary has been partially supported by the GAČR project, Czech Republic 17-09142S . Andreas Wiese has been partially supported by the grant Fondecyt Regular 1170223 . Funding Information: Hans Raj Tiwary has been partially supported by the GA?R project, Czech Republic17-09142S. Andreas Wiese has been partially supported by the grant Fondecyt Regular1170223. Publisher Copyright: © 2020 Elsevier B.V.

PY - 2020/7

Y1 - 2020/7

N2 - 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Ω(n∕logn), even if each job has size 1 or 2 and the optimal makespan is 2.

AB - 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Ω(n∕logn), even if each job has size 1 or 2 and the optimal makespan is 2.

KW - Extended formulations

KW - Linear programming

KW - Makespan scheduling

UR - http://www.scopus.com/inward/record.url?scp=85085576395&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85085576395&partnerID=8YFLogxK

U2 - 10.1016/j.orl.2020.05.008

DO - 10.1016/j.orl.2020.05.008

M3 - Article

AN - SCOPUS:85085576395

SN - 0167-6377

VL - 48

SP - 472

EP - 479

JO - Operations Research Letters

JF - Operations Research Letters

IS - 4

ER -

On the extension complexity of scheduling polytopes

Abstract

Bibliographical note

Keywords

UN SDGs

Access to Document

Persistent URL (handle)

Other files and links

Fingerprint

Cite this