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

## Abstract

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

Actions:

Content information:

Deposit Information:

ZAIK Number: | zpr93-143 |
---|---|

Depositing User: | Rainer Schrader |

Date Deposited: | 02 Apr 2001 00:00 |

Last Modified: | 04 Jul 2014 13:19 |

URI: | http://e-archive.informatik.uni-koeln.de/id/eprint/143 |