Near-Optimal Solutions and Large Integrality Gaps for Almost All Instances of Single-Machine Precedence-Constrained Scheduling

References

• Ambühl C., Mastrolilli M., Svensson O. Inapproximability results for sparsest cut, optimal linear arrangement, and precedence constrained scheduling. Proc. 48th Annual IEEE Sympos. Foundations Comput. Sci. (FOCS 2007) (2007) (IEEE Computer Society, Los Alamitos, CA) 329–337Crossref, Google Scholar
• Bansal N., Khot S. Optimal long code test with one free bit. Proc. 50th Annual IEEE Sympos. Foundations Comput. Sci. (FOCS 2009) (2009) (IEEE Computer Society, Los Alamitos, CA) 453–462Crossref, Google Scholar
• Chekuri C., Motwani R. Precedence constrained scheduling to minimize sum of weighted completion times on a single machine. Discrete Appl. Math. (1999) 98(1–2):29–38Crossref, Google Scholar
• Chudak F. A., Hochbaum D. S. A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine. Oper. Res. Lett. (1999) 25(5):199–204Crossref, Google Scholar
• Correa J. R., Schulz A. S. Single-machine scheduling with precedence constraints. Math. Oper. Res. (2005) 30(4):1005–1021Link, Google Scholar
• Eastman W. L., Even S., Isaacs I. M. Bounds for the optimal scheduling of n jobs on m processors. Management Sci. (1964) 11(2):268–279Link, Google Scholar
• Erdős P., Rényi A. On random graphs I. Publicationes Mathematicae (1959) 6:290–297Google Scholar
• Gallo G., Grigoriadis M. D., Tarjan R. E. A fast parametric maximum flow algorithm and applications. SIAM J. Comput. (1989) 18(1):30–55Crossref, Google Scholar
• Goemans M. X., Williamson D. P. Two-dimensional Gantt charts and a scheduling algorithm of Lawler. SIAM J. Discrete Math. (2000) 13(3):281–294Crossref, Google Scholar
• Graham R. L., Lawler E. L., Lenstra J. K., Rinnooy Kan A. H. G. Optimization and approximation in deterministic sequencing and scheduling: A survey. Ann. Discrete Math. (1979) 5:287–326Crossref, Google Scholar
• Hall L. A., Schulz A. S., Shmoys D. B., Wein J. Scheduling to minimize average completion time: Off-line and on-line approximation algorithms. Math. Oper. Res. (1997) 22(3):513–544Link, Google Scholar
• Hall P. On representatives of subsets. J. London Math. Soc. (1935) 10(1):26–30Crossref, Google Scholar
• Khot S. On the power of unique 2-prover 1-round games. Proc. 34th Annual ACM Sympos. Theory Comput. (STOC 2002) (2002) (ACM, New York) 767–775Crossref, Google Scholar
• Lawler E. L. Sequencing jobs to minimize total weighted completion time subject to precedence constraints. Ann. Discrete Math. (1978) 2:75–90Crossref, Google Scholar
• Lenstra J. K., Rinnooy Kan A. H. G. Complexity of scheduling under precedence constraints. Oper. Res. (1978) 26(1):22–35Link, Google Scholar
• Margot F., Queyranne M., Wang Y. Decompositions, network flows, and a precedence constrained single-machine scheduling problem. Oper. Res. (2003) 51(6):981–992Link, Google Scholar
• Mitzenmacher M., Upfal E.Probability and Computing: Randomized Algorithms and Probabilistic Analysis (2005) (Cambridge University Press, Cambridge, UK) Crossref, Google Scholar
• Picard J.-C., Queyranne M. On the structure of all minimum cuts in a network and applications. Math. Programming Stud. (1980) 13:8–16Crossref, Google Scholar
• Potts C. N. An algorithm for the single machine sequencing problem with precedence constraints. Math. Programming Stud. (1980) 13:78–87Crossref, Google Scholar
• Queyranne M., Wang Y. Single-machine scheduling polyhedra with precedence constraints. Math. Oper. Res. (1991) 16(1):1–20Link, Google Scholar
• Sidney J. B. Decomposition algorithms for single-machine sequencing with precedence constraints and deferral costs. Oper. Res. (1975) 23(2):283–298Link, Google Scholar
• Smith W. E. Various optimizers for single-stage production. Naval Res. Logist. Quart. (1956) 3(1-2):59–66Crossref, Google Scholar
• Woeginger G. J. On the approximability of average completion time scheduling under precedence constraints. Discrete Appl. Math. (2003) 131(1):237–252Crossref, Google Scholar