Facets of the generalized permutahedron of a poset

Arnim, Annelie von and Schulz, Andreas S. (1997) Facets of the generalized permutahedron of a poset.
Published in: Discrete Applied Mathematics Vol. 72 (1-2). pp. 179-192.


Given a poset P as a precedence relation on a set of jobs with processing time vector p, the generalized permutahedron ext{perm}(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 ext{perm}(P,p). Queyranne and Wang (1991) as well as von Arnim and Schrader (1997) 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 ext{perm}(P,p), and characterize the facet inducing inequalities under the known classes of valid inequalities.

Full text not available from this repository.
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr94-179
Depositing User: Archive Admin
Date Deposited: 02 Apr 2001 00:00
Last Modified: 28 Sep 2011 14:52
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/179