On the extension complexity of scheduling polytopes

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F20%3A10423976" target="_blank" >RIV/00216208:11320/20:10423976 - isvavai.cz</a>
Result on the web
<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=NwnB5Ch1cS" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=NwnB5Ch1cS</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.orl.2020.05.008" target="_blank" >10.1016/j.orl.2020.05.008</a>

Result language
angličtina
Original language name
On the extension complexity of scheduling polytopes
Original language description
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(Omega(n/logn)), even if each job has size 1 or 2 and the optimal makespan is 2. (C) 2020 Elsevier B.V. All rights reserved.
Czech name
—
Czech description
—

Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project
<a href="/en/project/GA17-09142S" target="_blank" >GA17-09142S: Modern algorithms: New challenges of complex data sets</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year
2020
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)