Single machine precedence constrained scheduling is a Vertex cover problem
From MaRDI portal
Recommendations
- Single Machine Precedence Constrained Scheduling Is a Vertex Cover Problem
- Single-Machine Scheduling with Precedence Constraints
- Single-Machine Scheduling Polyhedra with Precedence Constraints
- On the approximability of single-machine scheduling with precedence constraints
- An exact algorithm for the precedence-constrained single-machine scheduling problem
- Integer Programming and Combinatorial Optimization
- scientific article; zbMATH DE number 4181112
- Single machine scheduling with job-dependent convex cost and arbitrary precedence constraints
- scientific article; zbMATH DE number 1766737
- scientific article; zbMATH DE number 1487922
Cites work
- A fully combinatorial 2-approximation algorithm for precedence-constrained scheduling a single machine to minimize average weighted completion time
- A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine
- An algorithm for the single machine sequencing problem with precedence constraints
- Approximating Precedence-Constrained Single Machine Scheduling by Coloring
- Complexity of Scheduling under Precedence Constraints
- Decomposition Algorithms for Single-Machine Sequencing with Precedence Relations and Deferral Costs
- Decompositions, Network Flows, and a Precedence Constrained Single-Machine Scheduling Problem
- Efficient bounds for the stable set, vertex cover and set packing problems
- scientific article; zbMATH DE number 53952 (Why is no real title available?)
- scientific article; zbMATH DE number 1947426 (Why is no real title available?)
- scientific article; zbMATH DE number 6157240 (Why is no real title available?)
- Inapproximability Results for Maximum Edge Biclique, Minimum Linear Arrangement, and Sparsest Cut
- On the approximability of average completion time scheduling under precedence constraints.
- On the hardness of approximating minimum vertex cover
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
- Partial orders of dimension 2
- Polynomial time approximation algorithms for machine scheduling: Ten open problems
- Precedence constrained scheduling to minimize sum of weighted completion times on a single machine
- Properties of vertex packing and independence system polyhedra
- Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
- Scheduling with Precedence Constraints of Low Fractional Dimension
- Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints
- Single Machine Scheduling with Precedence Constraints of Dimension 2
- Single-Machine Scheduling with Precedence Constraints
- Some optimal inapproximability results
- Two-Dimensional Gantt Charts and a Scheduling Algorithm of Lawler
- Vertex packings: Structural properties and algorithms
Cited in
(16)- A survey on how the structure of precedence constraints may change the complexity class of scheduling problems
- 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
- An exact dynamic programming algorithm for the precedence-constrained class sequencing problem
- Vertex cover in graphs with locally few colors
- Approximating Precedence-Constrained Single Machine Scheduling by Coloring
- Scheduling results applicable to decision-theoretic troubleshooting
- The feedback arc set problem with triangle inequality is a vertex cover problem
- A General Framework for Approximating Min Sum Ordering Problems
- On Submodular Search and Machine Scheduling
- Single Machine Precedence Constrained Scheduling Is a Vertex Cover Problem
- Quantum speedup for solving the minimum vertex cover problem based on Grover search algorithm
- Hardness and approximation of submodular minimum linear ordering problems
- Combination of parallel machine scheduling and vertex cover
This page was built for publication: Single machine precedence constrained scheduling is a Vertex cover problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1016523)
