Efficient implementation of Carathéodory’s theorem for the single machine scheduling polytope

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)
22 Downloads (Pure)

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 Carathéodory’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 Grötschel, Lovász 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.
Original languageEnglish
Pages (from-to)136-145
Number of pages10
JournalDiscrete applied mathematics
Volume215
DOIs
Publication statusPublished - 31 Dec 2016

Fingerprint Dive into the research topics of 'Efficient implementation of Carathéodory’s theorem for the single machine scheduling polytope'. Together they form a unique fingerprint.

  • Cite this