The permutahedron of N-sparse posets

The permutahedron of N-sparse posets

0.00 Avg rating0 Votes
Article ID: iaor1998331
Country: Netherlands
Volume: 75
Issue: 1
Start Page Number: 1
End Page Number: 18
Publication Date: Oct 1996
Journal: Mathematical Programming
Authors: , ,
Keywords: posets, polyhedra
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.

Reviews

Required fields are marked *. Your email address will not be published.