The Permutahedron of N-sparse Posets

Arnim, Annelie von and Schrader, Rainer and Wang, Yaoguang (1996) The Permutahedron of N-sparse Posets.
Published in: Mathematical programming : Series A Vol. 75 (1). pp. 1-18.


The permutahedron of a poset is the convex hull of all incidence vectors of linear extensions. For the case of N-sparse posets in which any five elements induce at most one N we give a characterization of the permutahedron in terms of linear inequalities. This yields an LP-solution for minimizing the weighted mean completion time for jobs with unit processing times and N-sparse precedence constraints. We close with an extension of our approach to arbitrary processing times

Full text not available from this repository.
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr93-143
Depositing User: Rainer Schrader
Date Deposited: 02 Apr 2001 00:00
Last Modified: 04 Jul 2014 13:19