M. R. Garey
D. S. Johnson
- 1 AHO, A V, HOPCROFT, J E, AND ULLMAN, J D The Deszgn and Analysis of Computer Algorithms. Addison- Wesley, Reading, Mass, 1974 Google Scholar
- 2 COFFMAN, E G, AND GRAHAM, R L Optunal scheduling for two-processor systems. Acta Informat~ca 1 (1972), 200-213Google Scholar
- 3 DANTZIG, G B Discrete variable extremum problems. Oper Res 5 (1957), 266-277Google Scholar
- 4 GAREY, M R, AND JOHNSON, D S Complexity results for mulUprocessor scheduling under resource constraints SIAM J Comptng. 4 (1975), 397-41 lGoogle Scholar
- 5 GAREY, M R, AND JOHNSON, D S Two processor scheduhng wtth start ttmes and deadlines SlAM J. Comptng 6 (1977), 416-426Google Scholar
- 6 GAREY, M R, ANt) JOHNSON, D S The rectilinear Sterner tree problem ~s Npocomplete SIAM J Appl Math. 32 (1977), 826-834Google Scholar
- 7 GAREY, M R, JOHNSON, D S, AND SETHI, R The complexRy of flowshop and jobshop scheduling Math Oper Res 1 (1976), !17-129Google Scholar
- 8 GAREY, M R, JOHNSON, D S, AND STOCKMEYER, L Some sunphfied NP-complete graph problems Theoret. Comptr Scl 1 (1976), 237-267Google Scholar
- 9 GONZALEZ, T, AND SAHNI, S Flow shop and job shop schedules Tech Rep No 75-14, Dept of Comptr Sct, U of Mmnesota, Mmneapohs, Minn., 1975Google Scholar
- 10 HOROWITZ, E, AND SAHNI, S Exact and approxtmate algorithms for scheduling nomdenUcal processors J. A CM 23, 2 (April 1976), 317-327 Google Scholar
- 11 IBARRA, O H, AND KIM, C E Fast approximation algorithms for the knapsack and sum of subset problems J. ACM 22, 4 (Oct 1975), 463-468. Google Scholar
- 12 JOHNSON, D S, DEMERS, A, ULLMAN, J D, GAREY, M R, AND GRAHAM, R L Worst-case performance bounds for simple one-dunensional packing algorithms SIAM J Comptng 3 (1974), 299-325.Google Scholar
- 13 KARP, R M Reducibility among combmatonal problems. In Complextty of Computer Computauons, R.E. Miler and J W Thatcher, Eds, Plenum Press, New York, 1972, pp 85-104Google Scholar
- 14 KARl', R M On the complexity of combinatorial problems Networks 5 (1975), 45-68Google Scholar
- 15 LADNER, R E On the structure of polynomial time reduclblhty J ACM 22, l (Jan 1975), 155-171. Google Scholar
- 16 LAWLER, E L A "quasi-polynomial" algorithm for sequencing jobs to minimize total tardiness Memo No ERL-M558, Electron Res. Lab, U. of Cahforma, Berkeley, Cahf, 1975Google Scholar
- 17 LAWLER, E.L., AND MOORE, J.M. A functional equaUon and ~ts apphcatmn to resource allocation and sequencing problems Manage. Scz. 16 (1969), 77-84.Google Scholar
- 18 LENSTRA, J.K, RINNOO~ KAN, A H G, AND BRUCKER, P Complexity of machine scheduhng problems Annals Discrete Math 1 (1977), 343-362Google Scholar
- 19 NEMHAUSER, G L, AND YU, P.L A problem m bulk service scheduling Oper Res 20 (1972), 813-819Google Scholar
- 20 PAPADIMITRIOU, C H, AND STEIGLITZ, K Some complexity results for the travehng salesman problem Proc. 8th Annual ACM Syrup on Theory of Comptng, 1976, pp 1-9 Google Scholar
- 21 SAs~I, S. ComputatlonaUy related problems SIAM J Comptng. 3 (1974), 262-279Google Scholar
- 22 SAHNI, S Algorithms for scheduling independent tasks J ACM 23, 1 (Jan 1976), 116-127 Google Scholar
- 23 ULLMAN, J D NP-complete scheduhng problems. J Comptr Syst Sct I0 (1975), 384-393Google Scholar
Index Terms
- `` Strong '' NP-Completeness Results: Motivation, Examples, and Implications
Recommendations
Separating NP-Completeness Notions Under Strong Hypotheses
CCC '97: Proceedings of the 12th Annual IEEE Conference on Computational ComplexityJ.H. Lutz (1993) proposed the study of the structure of the class NP=NTIME(poly) under the hypothesis that NP does not have p-measure 0 (with respect to Lutz's resource bounded measure. J.H. Lutz and E. Mayordomo (1996) showed that, under this ...
Separating NP-Completeness Notions under Strong Hypotheses
Lutz (1993, “Proceedings of the Eight Annual Conference on Structure in Complexity Theory,” pp. 158 175) proposed the study of the structure of the class NP=NTIME(poly) under the hypothesis that NP does not have p-measure 0 (with respect to Lutz's ...
Partial Bi-immunity, Scaled Dimension, and NP-Completeness
The Turing and many-one completeness notions for NP have been previously separated under measure, genericity, and bi-immunity hypotheses on NP. The proofs of all these results rely on the existence of a language in NP with almost everywhere hardness.
In ...
Comments