Efficient implementation of Carathéodory's theorem for the single machine scheduling polytope

DOI10.1016/j.dam.2016.06.031zbMath1354.90109DBLPjournals/dam/HoeksmaMU16OpenAlexW2486473387WikidataQ62044130 ScholiaQ62044130MaRDI QIDQ323058

Ruben Hoeksma, Bodo Manthey, Marc Uetz

Publication date: 7 October 2016

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2016.06.031

zbMATH Keywords

Carathéodory's theoremzonotopesscheduling polytope

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27)

Related Items (1)

Quasi-Newton algorithm for optimal approximate linear regression design: optimization in matrix space

Cites Work

• Unnamed Item
• Unnamed Item
• Testing membership in matroid polyhedra
• On submodular function minimization
• The ellipsoid method and its consequences in combinatorial optimization
• Geometric algorithms and combinatorial optimization
• Structure of a simple scheduling polyhedron
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• Approximation Algorithms for Bounded Color Matchings via Convex Decompositions
• Iterative Packing for Demand and Hypergraph Matching
• Online Linear Optimization over Permutations
• A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
• Generalized Hypergraph Matching via Iterated Packing and Local Ratio
• Lectures on Polytopes
• Two Dimensional Optimal Mechanism Design for a Sequencing Problem
• Scheduling jobs that arrive over time

This page was built for publication: Efficient implementation of Carathéodory's theorem for the single machine scheduling polytope