Scheduling with Precedence Constraints of Low Fractional Dimension

DOI10.1007/978-3-540-72792-7_11MaRDI QIDQ5429263zbMATH OpenOpenAlexFDO

Authors Monaldo Mastrolilli, Nikolaus Mutsanas, Ola Svensson, Christoph Ambühl

Publication date 29 November 2007

Published in Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-72792-7_11

Mathematics Subject Classification ID

Approximation algorithms (68W25) Deterministic scheduling theory in operations research (90B35)

Recommendations

• On the approximability of single-machine scheduling with precedence constraints
• On the approximability of average completion time scheduling under precedence constraints.
• scientific article; zbMATH DE number 1754642
• Approximating Precedence-Constrained Single Machine Scheduling by Coloring
• scientific article; zbMATH DE number 5605136

Cited in

(12)

• Single machine precedence constrained scheduling is a Vertex cover problem
• On the approximability of average completion time scheduling under precedence constraints.
• Minimals Plus: an improved algorithm for the random generation of linear extensions of partially ordered sets
• An exact algorithm for the precedence-constrained single-machine scheduling problem
• On the approximability of single-machine scheduling with precedence constraints
• Vertex cover in graphs with locally few colors
• Precedence-Constrained Scheduling Problems Parameterized by Partial Order Width
• Single Machine Scheduling with Precedence Constraints of Dimension 2
• scientific article; zbMATH DE number 5605136 (Why is no real title available?)
• Approximating Precedence-Constrained Single Machine Scheduling by Coloring
• scientific article; zbMATH DE number 1754642 (Why is no real title available?)
• Quasi-PTAS for scheduling with precedences using LP hierarchies

This page was built for publication: Scheduling with Precedence Constraints of Low Fractional Dimension

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