@book{f59841aadf3f408680864afa0211ee40,
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\textbackslash{}in C\$, Carath\textbackslash{}'eodory'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 \textbackslash{}bigO\{n\textasciicircum{}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\{\textbackslash{}{"}o\}tschel, Lov\{\textbackslash{}'a\}sz, and Schrijver applied to one of these subpolytopes.",
keywords = "METIS-300180, IR-88292, EWI-24630, Polyhedral subdivision, Algorithms, Zonotopes, Scheduling polytope, Convex combination, Decomposition, Polyhedral theory",
author = "R.P. Hoeksma and Bodo Manthey and Uetz, \{Marc Jochen\}",
year = "2013",
month = dec,
day = "4",
language = "Undefined",
series = "CTIT Technical Report Series",
publisher = "Centre for Telematics and Information Technology (CTIT)",
number = "TR-CTIT-13-25",
address = "Netherlands",
}