On the Approximability of Single-Machine Scheduling with Precedence Constraints

References

• Alimonti P., Kann V. Some APX-completeness results for cubic graphs. Theoret. Comput. Sci. (2000) 237(1–2):123–134Crossref, Google Scholar
• Ambühl C., Mastrolilli M. Single machine precedence constrained scheduling is a vertex cover problem. Algorithmica (2009) 53(4):488–503Crossref, Google Scholar
• Ambühl C., Mastrolilli M., Svensson O., Dray J., Jansen K., Rolim J. D. P., Zwick U. Approximating precedence-constrained single machine scheduling. Proc. 9th Internat. Workshop Approximation Algorithms Combin. Optim. Problems (APPROX2006), Approximation, Randomization, and Combinatorial Optimization Algorithms and Techniques, Vol. 4110 (2006) (Springer, Berlin) 15–26Lecture Notes in Computer ScienceCrossref, Google Scholar
• Ambühl C., Mastrolilli M., Svensson O. Inapproximability results for sparsest cut, optimal linear arrangement, and precedence constraint scheduling. Proc. 48th Annual IEEE Sympos. Foundations Comput. Sci. (2007) (IEEE, Washington, DC) 329–337Google Scholar
• Ambühl C., Mastrolilli M., Mutsanas N., Svensson O., Fischetti M., Williamson D. P. Scheduling with precedence constaints of low fractional dimension. Proc. 12th Internat. IPCO Conf. (IPCO2007), Integer Programming and Combinatorial Optimization, Vol. 4513 (2007) (Springer, Berlin) 130–144Lecture Notes in Computer ScienceCrossref, Google Scholar
• Bansal N., Khot S. Optimal long-code test with one free bit. Proc. 50th Annual IEEE Sympos. Foundations Comput. Sci. (FOCS) (2009) (IEEE, Washington, DC) 453–462Crossref, Google Scholar
• Brightwell G. R., Scheinerman E. R. Fractional dimension of partial orders. Order (1992) 9(2):139–158Crossref, 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
• Felsner S., Trotter W. T. On the fractional dimension of partially ordered sets. Discrete Math. (1994) 136(1-3):101–117Crossref, Google Scholar
• Felsner S., Trotter W. T. Dimension, graph and hypergraph coloring. Order (2000) 17(2):167–177Crossref, Google Scholar
• Garey M. R., Johnson D. S., Stockmeyer L. J. Some simplified NP-complete graph problems. Theoret. Comput. Sci. (1976) 1(3):237–267Crossref, 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., Lawler E., Lenstra J. K., Rinnooy Kan A. H. G. Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics (1979) 5(North-Holland, Amsterdam) 287–326Google Scholar
• Hall L. A., Shmoys D. B., Wein J. Scheduling to minimize average completion time: Off-line and on-line algorithms. Sympos. Discrete Algorithms (SODA) (1996) 7(Society of Industrial and Applied Mathematics, Philadelphia) 142–151Google 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
• Hegde R., Jain K. The hardness of approximating poset dimension. Electronic Notes Discrete Math. (2007) 29:435–443Crossref, Google Scholar
• Hochbaum D. S. Efficient bounds for the stable set, vertex cover and set packing problems. Discrete Appl. Math. (1983) 6(3):243–254Crossref, Google Scholar
• Khot S. On the power of unique 2-prover 1-round games. Proc. 34th Annual ACM Sympos. Theory Comput. (STOC) (2002) (ACM, New York) 767–775Crossref, Google Scholar
• Kolliopoulos S. G., Steiner G. Partially-ordered knapsack and applications to scheduling. Proc. 10th Annual Eur. Sympos. Algorithms (ESA) (2002) (Springer, Berlin) 612–624Crossref, 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
• Lawler E. L., Lenstra J. K., Rinnooy Kan A. H. G., Shmoys D. B., Graves S. C., Rinnooy Kan A. H. G., Zipkin P. Sequencing and scheduling: Algorithms and complexity. Handbooks in Operations Research and Management Science (1993) 4(North-Holland, Amsterdam) 445–552Google Scholar
• Lenstra J. K., Rinnooy Kan A. H. G. The complexity of scheduling under precedence constraints. Oper. Res. (1978) 26(1):22–35Link, Google Scholar
• Ma T.-H., Spinrad J. P. On the 2-chain subgraph cover and related problems. J. Algorithms (1994) 17(2):251–268Crossref, 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
• Möhring R. H., Rival L. Computationally tractable classes of ordered sets. Algorithms and Order (1989) (Kluwer Academic, Dordrecht, The Netherlnads) 105–193Crossref, Google Scholar
• Nemhauser G. L., Trotter L. E. Vertex packings: Structural properties and algorithms. Math. Programming (1975) 8(1):232–248Crossref, Google Scholar
• Papadimitriou C. H., Yannakakis M. Scheduling interval-ordered tasks. SIAM J. Comput. (1979) 8(3):405–409Crossref, Google Scholar
• Pisaruk N. N. A fully combinatorial 2-approximation algorithm for precedence-constrained scheduling a single machine to minimize average weighted completion time. Discrete Appl. Math. (2003) 131(3):655–663Crossref, 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
• Rabinovitch I. The dimension of semiorders. J. Combin. Theory Ser. A (1978) 25:50–61Crossref, Google Scholar
• Scheinerman E. R., Ullman D. H.Fractional Graph Theory (1997) (John Wiley and Sons, New York) Google Scholar
• Schulz A. S. Scheduling to minimize total weighted completion time: Performance guarantees of LP-based heuristics and lower bounds. Proc. 5th Conf. Integer Programming Combin. Optim. (IPCO), Vol. 1084 (1996) (Springer, Berlin) 301–315Lecture Notes in Computer ScienceCrossref, Google Scholar
• Schuurman P., Woeginger G. J. Polynomial time approximation algorithms for machine scheduling: Ten open problems. J. Scheduling (1999) 2(5):203–213Crossref, Google Scholar
• Sidney J. B. Decomposition algorithms for single-machine sequencing with precedence relations and deferral costs. Oper. Res. (1975) 23(2):283–298Link, Google Scholar
• Spencer J. On minimum scrambling sets of simple orders. Acta Mathematica (1971) 22(3–4):349–353Google Scholar
• Svensson O.Approximability of Some Classical Graph and Scheduling Problems (2009) . Ph.D. thesis, Università della Svizzera Italiana, University of Lugano, Lugano, SwitzerlandGoogle Scholar
• Svensson O. Conditional hardness of precedence constrained scheduling on identical machines. Proc. 42nd ACM Sympos. Theory Comput. (STOC) (2010) (ACM, New York) 745–754Crossref, Google Scholar
• Trotter W. T.Combinatorics and Partially Ordered Sets: Dimension Theory (1992) (The Johns Hopkins University Press, Baltimore) Johns Hopkins Series in the Mathematical SciencesGoogle Scholar
• Trotter W. T., Bailey R. A. New perspectives on interval orders and interval graphs. Surveys in Combinatorics (1997) 241(London)237–286Mathematical Society Lecture Note SeriesGoogle Scholar
• Uhan N. A.Algorithmic and Game-Theoretic Perspectives on Scheduling (2008) . Ph.D. thesis, Massachusetts Institute of Technology, Cambridge, MAGoogle 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
• Yannakakis M. On the complexity of partial order dimension problem. SIAM J. Algebraic Discrete Methods (1982) 22(3):351–358Crossref, Google Scholar