@inproceedings{cd48a36f5c5149c8b7d8229d1e471249,

title = "Decomposition algorithm for the single machine scheduling polytope",

abstract = "Given an $n$-vector $p$ of processing times of jobs, the single machine scheduling polytope $C$ arises as the convex hull of completion times of jobs when these are scheduled without idle time on a single machine. Given a point $x\in C$, Carath{\'e}odory's theorem implies that $x$ can be written as convex combination of at most $n$ vertices of $C$. We show that this convex combination can be computed from $x$ and $p$ in time \bigO{n^2}, which is linear in the naive encoding of the output. We obtain this result using essentially two ingredients. First, we build on the fact that the scheduling polytope is a zonotope. Therefore, all of its faces are centrally symmetric. Second, instead of $C$, we consider the polytope $Q$ of half times and its barycentric subdivision. We show that the subpolytopes of this barycentric subdivison of $Q$ have a simple, linear description. The final decomposition algorithm is in fact an implementation of an algorithm proposed by Gr{\"o}tschel, Lov{\'a}sz, and Schrijver applied to one of these subpolytopes.",

keywords = "Polyhedral subdivision, Polyhedral theory, EWI-24927, Decomposition, METIS-305955, Scheduling polytope, Zonotopes, IR-91477, Algorithms, Convex combination",

author = "R.P. Hoeksma and Bodo Manthey and Uetz, {Marc Jochen}",

note = "10.1007/978-3-319-09174-7_24 ; Combinatorial Optimization, Third International Symposium, ISCO 2014 ; Conference date: 05-03-2014 Through 07-03-2014",

year = "2014",

month = mar,

day = "5",

doi = "10.1007/978-3-319-09174-7_24",

language = "Undefined",

isbn = "978-3-319-09173-0",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "280--291",

booktitle = "Combinatorial Optimization, Third International Symposium, ISCO 2014",

}