Base polytopes of series-parallel posets: Linear description and optimization
Schrader, Rainer and Schulz, Andreas S. and Wambach, Georg
Base polytopes of series-parallel posets: Linear description and optimization.
Published in: Mathematical Programming Vol. 82 (1-2). pp. 159-173.
We define the base polytope B(P,g) of a partially ordered set P and a supermodular function g on the ideals of P as the convex hull of the incidence vectors of all linear extensions of P. This new class of polytopes contains, among others, the base polytopes of supermodular systems and permutahedra as special cases. After introducing the notion of compatibility for g, we give a complete linear description of B(P,g) for series--parallel posets and compatible functions g. In addition, we describe a greedy-type procedure which exhibits Sidney's job sequencing algorithm to minimize the total weighted completion time as a natural extension of the matroidal greedy algorithm from sets to posets.
|Citations:||0 (Google Scholar) | 0 (Web of Science)|
|Uncontrolled Keywords:||base polytopes greedy algorithm integer programming polyhedral combinatorics series-parallel posets supermodular functions|
|Divisions:||Institute of Computer Science > Computer Science Department - Prof. Dr. Schrader|
|Depositing User:||Rainer Schrader|
|Date Deposited:||02 Apr 2001 00:00|
|Last Modified:||16 Jan 2012 16:24|