A General Scheme for Designing Monotone Algorithms for Scheduling Problems with Precedence Constraints

DOI10.1007/978-3-540-93980-1_9zbMATH Open1209.90187OpenAlexW2138846348MaRDI QIDQ3602833FDOQ3602833

Authors Clemens Thielen, Sven O. Krumke

Publication date 12 February 2009

Published in Approximation and Online Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-93980-1_9

zbMATH Keywords

schedulingprecedence constraintsalgorithmic mechanism designmonotone algorithms

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Auctions, bargaining, bidding and selling, and other market models (91B26) Approximation algorithms (68W25)

Recommendations

• Approximation and Online Algorithms
• Deterministic monotone algorithms for scheduling on related machines
• An improved monotone algorithm for scheduling related machines with precedence constraints
• Algorithms – ESA 2005
• A unified approach to truthful scheduling on related machines

Cites work

• scientific article; zbMATH DE number 1187165 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 871909 (Why is no real title available?)
• A monotone approximation algorithm for scheduling with precedence constraints
• Algorithms – ESA 2005
• Approximation Algorithms for Precedence-Constrained Scheduling Problems on Parallel Machines that Run at Different Speeds
• Bounds for Certain Multiprocessing Anomalies
• Online algorithms. The state of the art
• STACS 2004
• STACS 2005
• Scheduling algorithms
• Structural Information and Communication Complexity
• Structure of a simple scheduling polyhedron

Cited in

(7)

• Deterministic monotone algorithms for scheduling on related machines
• A monotone approximation algorithm for scheduling with precedence constraints
• Approximation and Online Algorithms
• An improved monotone algorithm for scheduling related machines with precedence constraints
• Algorithms – ESA 2005
• Multistage interval scheduling games
• Scheduling with bully selfish jobs

This page was built for publication: A General Scheme for Designing Monotone Algorithms for Scheduling Problems with Precedence Constraints

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