On the extension complexity of scheduling
| Author | dc.contributor.author | Tiwary, Hans Raj | |
| Author | dc.contributor.author | Verdugo, Víctor | |
| Author | dc.contributor.author | Wiese, Andreas | |
| Admission date | dc.date.accessioned | 2020-10-01T20:50:53Z | |
| Available date | dc.date.available | 2020-10-01T20:50:53Z | |
| Publication date | dc.date.issued | 2020 | |
| Cita de ítem | dc.identifier.citation | Operations Research Letters. Vol. 48, No. 4, July 2020: 472-479 | es_ES |
| Identifier | dc.identifier.other | 10.1016/j.orl.2020.05.008 | |
| Identifier | dc.identifier.uri | https://repositorio.uchile.cl/handle/2250/176948 | |
| Abstract | 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. | es_ES |
| Patrocinador | dc.description.sponsorship | GACR project, Czech Republic 17-09142S Comisión Nacional de Investigación Científica y Tecnológica (CONICYT) CONICYT FONDECYT 1170223 | es_ES |
| Lenguage | dc.language.iso | en | es_ES |
| Publisher | dc.publisher | Elsevier | es_ES |
| Type of license | dc.rights | Attribution-NonCommercial-NoDerivs 3.0 Chile | * |
| Link to License | dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/3.0/cl/ | * |
| Source | dc.source | Operations Research Letters | es_ES |
| Keywords | dc.subject | Extended formulations | es_ES |
| Keywords | dc.subject | Makespan scheduling | es_ES |
| Keywords | dc.subject | Linear programming | es_ES |
| Título | dc.title | On the extension complexity of scheduling | es_ES |
| Document type | dc.type | Artículo de revista | es_ES |
| dcterms.accessRights | dcterms.accessRights | Acceso Abierto | |
| Cataloguer | uchile.catalogador | ctc | es_ES |
| Indexation | uchile.index | Artículo de publicación ISI | |
| Indexation | uchile.index | Artículo de publicación SCOPUS |
Files in this item
This item appears in the following Collection(s)
-
Artículos de revistas
Artículos de revistas
Except where otherwise noted, this item's license is described as Attribution-NonCommercial-NoDerivs 3.0 Chile