ISSN:
1436-4646
Keywords:
Polyhedral combinatorics
;
Series—parallel posets
;
Base polytopes
;
Supermodular functions
;
Greedy algorithm
;
Integer programming
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract We define the base polytopeB(P, g) of a partially ordered setP and a supermodular functiong on the ideals ofP as the convex hull of the incidence vectors of all linear extensions ofP. 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 forg, we give a complete linear description ofB(P, g) for series—parallel posets and compatible functionsg. 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. © 1998 The Mathematical Programing Society, Inc. Published by Elsevier Science B.V.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01585869
Permalink
