Facets of the generalized permutahedron of a poset

✍ Scribed by Annelie von Arnim; Andreas S. Schulz

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 878 KB
• Volume: 72
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(96)00044-3

✦ Synopsis

Given a poset P as a precedence relation on a set of jobs with processing time vector p, the generalized permutahedron pem(P, p) of P is defined as the convex hull of all job completion time vectors corresponding to a linear extension of P. Thus, the generalized permutahedron allows for the single machine weighted flowtime scheduling problem to be formulated as a linear programming problem over perm(P, p). Queyranne and Wang [8] as well as von Arnim and Schrader [2] gave a collection of valid inequalities for this polytope. Here we present a description of its geometric structure that depends on the series decomposition of the poset P, prove a dimension formula for perm(P, p), and characterize the facet inducing inequalities under the known classes of valid inequalities.