Decomposition algorithm for the single machine scheduling polytope

DOI10.1007/978-3-319-09174-7_24MaRDI QIDQ3195338zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Ruben Hoeksma, Bodo Manthey, Marc Uetz

Publication date 16 October 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://research.utwente.nl/en/publications/decomposition-algorithm-for-the-single-machine-scheduling-polytope(cd48a36f-5c51-49c8-b7d8-229d1e471249).html

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Special polytopes (linear programming, centrally symmetric, etc.) (52B12)

Recommendations

• Efficient implementation of Carathéodory's theorem for the single machine scheduling polytope
• Structure of a simple scheduling polyhedron
• Decompositions, Network Flows, and a Precedence Constrained Single-Machine Scheduling Problem
• A polyhedral approach to single-machine scheduling problems.
• On the facial structure of scheduling polyhedra

Cites work

• scientific article; zbMATH DE number 1187165 (Why is no real title available?)
• scientific article; zbMATH DE number 1182907 (Why is no real title available?)
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• Decomposition algorithm for the single machine scheduling polytope
• Geometric algorithms and combinatorial optimization
• Lectures on Polytopes
• On submodular function minimization
• Online linear optimization over permutations
• Scheduling jobs that arrive over time
• Structure of a simple scheduling polyhedron
• Testing membership in matroid polyhedra
• The ellipsoid method and its consequences in combinatorial optimization
• Two dimensional optimal mechanism design for a sequencing problem

Cited in

(8)

• A game theoretic approach to a problem in polymatroid maximization
• Optimal mechanism design for a sequencing problem with two-dimensional types
• A decomposition property of polyhedra
• Polynomial algorithms for single machine scheduling problems with financial constraints
• Variations on the integral decomposition property
• Efficient implementation of Carathéodory's theorem for the single machine scheduling polytope
• Structure of a simple scheduling polyhedron
• Decomposition algorithm for the single machine scheduling polytope

This page was built for publication: Decomposition algorithm for the single machine scheduling polytope

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3195338)