Approximating Precedence-Constrained Single Machine Scheduling by Coloring

DOI10.1007/11830924_4MaRDI QIDQ3595374zbMATH OpenOpenAlexFDO

Authors Monaldo Mastrolilli, Ola Svensson, Christoph Ambühl

Publication date 28 August 2007

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11830924_4

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
• scientific article; zbMATH DE number 5605136
• Single Machine Precedence Constrained Scheduling Is a Vertex Cover Problem
• Scheduling with Precedence Constraints of Low Fractional Dimension
• Single machine precedence constrained scheduling is a Vertex cover problem

Cited in

(9)

• Single machine precedence constrained scheduling is a Vertex cover problem
• Cross-series-parallel digraphs
• An exact algorithm for the precedence-constrained single-machine scheduling problem
• An exact dynamic programming algorithm for the precedence-constrained class sequencing problem
• On the approximability of single-machine scheduling with precedence constraints
• Vertex cover in graphs with locally few colors
• Single Machine Scheduling with Precedence Constraints of Dimension 2
• Scheduling with Precedence Constraints of Low Fractional Dimension
• Single Machine Precedence Constrained Scheduling Is a Vertex Cover Problem

This page was built for publication: Approximating Precedence-Constrained Single Machine Scheduling by Coloring

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