Single machine precedence constrained scheduling is a Vertex cover problem
From MaRDI portal
Publication:1016523
DOI10.1007/s00453-008-9251-6zbMath1183.68102OpenAlexW2093392878MaRDI QIDQ1016523
Monaldo Mastrolilli, Christoph Ambühl
Publication date: 6 May 2009
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-008-9251-6
Related Items
A survey on how the structure of precedence constraints may change the complexity class of scheduling problems, A General Framework for Approximating Min Sum Ordering Problems, An exact dynamic programming algorithm for the precedence-constrained class sequencing problem, Quantum speedup for solving the minimum vertex cover problem based on Grover search algorithm, 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, Vertex Cover in Graphs with Locally Few Colors, A 2.542-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective, Parameterized complexity of machine scheduling: 15 open problems, Single-machine scheduling with an external resource, An exact algorithm for the precedence-constrained single-machine scheduling problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the hardness of approximating minimum vertex cover
- Efficient bounds for the stable set, vertex cover and set packing problems
- On the approximability of average completion time scheduling under precedence constraints.
- A fully combinatorial 2-approximation algorithm for precedence-constrained scheduling a single machine to minimize average weighted completion time
- Polynomial time approximation algorithms for machine scheduling: Ten open problems
- Precedence constrained scheduling to minimize sum of weighted completion times on a single machine
- A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine
- Inapproximability Results for Maximum Edge Biclique, Minimum Linear Arrangement, and Sparsest Cut
- Single Machine Scheduling with Precedence Constraints of Dimension 2
- Approximating Precedence-Constrained Single Machine Scheduling by Coloring
- Decompositions, Network Flows, and a Precedence Constrained Single-Machine Scheduling Problem
- An algorithm for the single machine sequencing problem with precedence constraints
- Decomposition Algorithms for Single-Machine Sequencing with Precedence Relations and Deferral Costs
- Vertex packings: Structural properties and algorithms
- Complexity of Scheduling under Precedence Constraints
- Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
- Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
- Two-Dimensional Gantt Charts and a Scheduling Algorithm of Lawler
- Properties of vertex packing and independence system polyhedra
- Single-Machine Scheduling with Precedence Constraints
- Scheduling with Precedence Constraints of Low Fractional Dimension
- Some optimal inapproximability results
- Partial orders of dimension 2
