On the Approximability of Single-Machine Scheduling with Precedence Constraints

DOI10.1287/moor.1110.0512zbMath1238.90059OpenAlexW2058023231MaRDI QIDQ2884295

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

Publication date: 24 May 2012

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/moor.1110.0512

zbMATH Keywords

single-machine schedulingvertex coverfractional dimension

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics of partially ordered sets (06A07) Deterministic scheduling theory in operations research (90B35) Coloring of graphs and hypergraphs (05C15) Approximation algorithms (68W25)

Related Items (10)

A survey on how the structure of precedence constraints may change the complexity class of scheduling problems ⋮ A \((2 + \epsilon)\)-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective ⋮ On Submodular Search and Machine Scheduling ⋮ Scheduling results applicable to decision-theoretic troubleshooting ⋮ The feedback arc set problem with triangle inequality is a vertex cover problem ⋮ A 2.542-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective ⋮ Online Linear Optimization for Job Scheduling Under Precedence Constraints ⋮ Polynomial Time Approximation Schemes for the Traveling Repairman and Other Minimum Latency Problems ⋮ Decision diagrams for solving a job scheduling problem under precedence constraints ⋮ Approximability of scheduling problems with resource consuming jobs

This page was built for publication: On the Approximability of Single-Machine Scheduling with Precedence Constraints