Efficient implementation of Carathéodory’s theorem for the single machine scheduling polytope
Author
dc.contributor.author
Hoeksma, Ruben
Author
dc.contributor.author
Manthey, Bodo
Author
dc.contributor.author
Uetz, Marc
Admission date
dc.date.accessioned
2017-04-04T19:38:11Z
Available date
dc.date.available
2017-04-04T19:38:11Z
Publication date
dc.date.issued
2016
Cita de ítem
dc.identifier.citation
Discrete Applied Mathematics 215 (2016) 136–145
es_ES
Identifier
dc.identifier.other
10.1016/j.dam.2016.06.031
Identifier
dc.identifier.uri
https://repositorio.uchile.cl/handle/2250/143460
Abstract
dc.description.abstract
In a fundamental paper in polyhedral combinatorics, Queyranne describes the complete facial structure of a classical object in combinatorial optimization, the single machine scheduling polytope. In the same paper, he answers essentially all relevant algorithmic questions with respect to optimization and separation. In the present paper, motivated by recent applications in the design of optimal incentive compatible mechanisms, we address an algorithmic question that was apparently not addressed before. Namely, we turn Caratheodory's theorem into an algorithm, and ask to write an arbitrary point in the scheduling polytope as a convex combination of the vertices of the polytope. We give a combinatorial O(n(2)) time algorithm, which is linear in the naive encoding of the output size. We obtain this result by exploiting the fact that the scheduling polytope is a zonotope, and by the observation that its barycentric subdivision has a simple, linear description. The actual decomposition algorithm is an implementation of a method proposed by Grotschel, Lovasz and Schrijver, applied to one of the subpolytopes of the barycentric subdivision. We thereby also shed new light on an algorithm recently proposed for a special case, namely the permutahedron
es_ES
Patrocinador
dc.description.sponsorship
Millennium Nucleus Information and Coordination in Networks ICM/FIC RC130003