Single Machine Precedence Constrained Scheduling Is a Vertex Cover Problem
- 1 January 2006
- book chapter
- Published by Springer Nature
- p. 28-39
Abstract
No abstract availableKeywords
This publication has 26 references indexed in Scilit:
- On the hardness of approximating vertex coverAnnals of Mathematics, 2005
- A fully combinatorial 2-approximation algorithm for precedence-constrained scheduling a single machine to minimize average weighted completion timeDiscrete Applied Mathematics, 2003
- On the approximability of average completion time scheduling under precedence constraintsDiscrete Applied Mathematics, 2003
- A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machineOperations Research Letters, 1999
- Precedence constrained scheduling to minimize sum of weighted completion times on a single machineDiscrete Applied Mathematics, 1999
- A survey of approximately optimal solutions to some covering and packing problemsACM Computing Surveys, 1997
- Approximation algorithms for NP-complete problems on planar graphsJournal of the ACM, 1994
- Efficient bounds for the stable set, vertex cover and set packing problemsDiscrete Applied Mathematics, 1983
- Partial orders of dimension 2Networks, 1972
- Various optimizers for single‐stage productionNaval Research Logistics Quarterly, 1956