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:
Full text not available from this repository.
Export as:
Editorial actions: View Item View Item (Login required)
Content information:
Item Type: Article
Citations: No citation data.
Uncontrolled Keywords: combinatorial optimization greedy algorithm integer polyhedra precedence constraints series-parallel posets weighted completion time scheduling
Subjects:
  • 90-XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C10 Integer programming

  • 52-XX Convex and discrete geometry > 52Bxx Polytopes and polyhedra > 52B12 Special polytopes (linear programming, centrally symmetric, etc.)

  • 90-XX Operations research, mathematical programming > 90Bxx Operations research and management science > 90B35 Scheduling theory, deterministic

  • 90-XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C27 Combinatorial optimization

    		•
    Divisions: Institute of Computer Science > Computer Science Department - Prof. Dr. Schrader
    Related URLs:
    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