On the extension complexity of scheduling polytopes

UOH Academic Repository

dc.contributor.author	Tiwary, HR
dc.contributor.author	Verdugo, V
dc.contributor.author	Wiese, A
dc.date.accessioned	2024-01-17T15:55:07Z
dc.date.available	2024-01-17T15:55:07Z
dc.date.issued	2020
dc.identifier.uri	https://repositorio.uoh.cl/handle/611/721
dc.description.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(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.
dc.description.sponsorship	GACR project, Czech Republic
dc.description.sponsorship	grant Fondecyt Regular(Comision Nacional de Investigacion Cientifica y Tecnologica (CONICYT)CONICYT FONDECYT)
dc.relation.uri	http://dx.doi.org/10.1016/j.orl.2020.05.008
dc.subject	Extended formulations
dc.subject	Makespan scheduling
dc.subject	Linear programming
dc.title	On the extension complexity of scheduling polytopes
dc.type	Artículo
uoh.revista	OPERATIONS RESEARCH LETTERS
dc.identifier.doi	10.1016/j.orl.2020.05.008
dc.citation.volume	48
dc.citation.issue	4
dc.identifier.orcid	Tiwary, Hans Raj/0000-0003-1903-1600
dc.identifier.orcid	Verdugo, Victor/0000-0003-0817-7356
dc.identifier.orcid	Wiese, Andreas/0000-0003-3705-016X
uoh.indizacion	Web of Science