Base polytopes of series-parallel posets: Linear description and optimization

DOI10.1007/BF01585869zbMath0920.90125MaRDI QIDQ1290639

Georg Wambach, Rainer Schrader, Andreas S. Schulz

Publication date: 3 June 1999

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

zbMATH Keywords

greedy algorithmpolyhedral combinatoricssupermodular functiontotal weighted completion timeseries-parallel posetsbase polytopes

Mathematics Subject Classification ID

Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Integer programming (90C10) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27)

Cites Work

• Pseudomatroids
• Generalized polymatroids and submodular flows
• Submodular functions and optimization
• Submodular linear programs on forests
• The permutahedron of \(N\)-sparse posets
• On a property of the class of n-colorable graphs
• Single-Machine Scheduling Polyhedra with Precedence Constraints
• Decomposition Algorithms for Single-Machine Sequencing with Precedence Relations and Deferral Costs
• Facets of the knapsack polytope
• Adjacent Vertices on a Permutohedron
• Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints
• A Rearrangement Inequality and the Permutahedron
• The permutahedron of series-parallel posets
• The permutahedron of series-parallel posets
• Facets of the generalized permutahedron of a poset