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

DOI10.1016/J.DAM.2016.06.031zbMATH Open1354.90109DBLPjournals/dam/HoeksmaMU16OpenAlexW2486473387WikidataQ62044130 ScholiaQ62044130MaRDI QIDQ323058FDOQ323058

Authors: 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

Recommendations

• A polyhedral approach to single-machine scheduling problems.
• Decomposition algorithm for the single machine scheduling polytope
• Near-optimal solutions of large-scale single-machine scheduling problems
• Pseudopolynomial algorithms for CTV minimization in single machine scheduling
• Single-Machine Scheduling Polyhedra with Precedence Constraints
• A family of inequalities valid for the robust single machine scheduling polyhedron
• Algorithms for some maximization scheduling problems on a single machine
• scientific article; zbMATH DE number 1031378
• scientific article; zbMATH DE number 4191384
• Algorithms and complexity analysis for robust single-machine scheduling problems

zbMATH Keywords

zonotopesscheduling polytopeCarathéodory's theorem

Mathematics Subject Classification ID

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

Cites Work

• Lectures on Polytopes
• Geometric algorithms and combinatorial optimization
• The ellipsoid method and its consequences in combinatorial optimization
• Title not available (Why is that?)
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• Testing membership in matroid polyhedra
• On submodular function minimization
• Structure of a simple scheduling polyhedron
• Approximation Algorithms for Bounded Color Matchings via Convex Decompositions
• Iterative packing for demand and hypergraph matching
• Online linear optimization over permutations
• Generalized hypergraph matching via iterated packing and local ratio
• Title not available (Why is that?)
• Two dimensional optimal mechanism design for a sequencing problem
• Scheduling jobs that arrive over time

Cited In (2)

• Quasi-Newton algorithm for optimal approximate linear regression design: optimization in matrix space
• Decomposition algorithm for the single machine scheduling polytope

This page was built for publication: Efficient implementation of Carathéodory's theorem 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 Q323058)