# 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.

## Abstract

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.

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 |