On the extension complexity of scheduling polytopes
Tiwary, H. R., Verdugo, V. & Wiese, A.
(2020).
On the extension complexity of scheduling polytopes.
Operations Research Letters,
48(4), 472-479.
https://doi.org/10.1016/j.orl.2020.05.008
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.
| Item Type | Article |
|---|---|
| Copyright holders | © 2020 Elsevier B.V. |
| Departments | LSE > Academic Departments > Mathematics |
| DOI | 10.1016/j.orl.2020.05.008 |
| Date Deposited | 10 Aug 2022 |
| Acceptance Date | 07 May 2020 |
| URI | https://researchonline.lse.ac.uk/id/eprint/115954 |