Michael Garey - Publications

  1. The Transitive Reduction of a Directed Graph, A. V. Aho, M. R. Garey and J. D. Ullman, SIAM J. Computing, 1:2 (1972), pp. 131-137.
  2. Optimal Binary Identification Procedures, M. R. Garey, SIAM J. Appl. Math., 23:2 (1972), pp. 173-186.
  3. Optimal Test Point Selection for Sequential Manufacturing Processes, M. R. Garey, Bell Sys. Tech. J., 51:1 (1972), pp. 291-300.
  4. Resident Bubble Cellular Logic Using Magnetic Domains, M. R. Garey, IEEE Trans. on Computers, C-21 (April 1972), pp. 392-396.
  5. Simple Binary Identification Problems, M. R. Garey, IEEE Trans. on Computers, C-21 (June 1972), pp. 588-590.
  6. On Enumerating Tournaments That Admit Exactly One Hamiltonian Circuit, M. R. Garey, J. Comb. Theory A, 13 (December 1972), pp. 266-269.
  7. Worst Case Analysis of Memory Allocation Algorithms, M. R. Garey, R. L. Graham and J. D. Ullman, Proc. 4th ACM Symp. Theory of Computing, 1972, pp. 143-150.
  8. Computing an Averaged Cost Allocation for Interrelated Operations, W. M. Boyce and M. R. Garey, IEEE Trans. on Manufacturing Technology, MFT-2 (1973), pp. 15-22.
  9. Optimal Task Sequencing With Precedence Constraints, M. R. Garey, Discrete Math., 4 (January 1973), pp. 37-56.
  10. Bounds on Scheduling With Limited Resources, M. R. Garey and R. L. Graham, Proc. 4th ACM Symp. Operating Systems Principles, October 1973, pp. 104-111.
  11. An Analysis of Some Packing Algorithms, M. R. Garey, R. L. Graham and J. D. Ullman, Combinatorial Algorithms, R Rustin (editor), Algorithmics Press, 1973, pp. 39-48.
  12. Optimal Binary Search Trees with Restricted Maximal Depth, M. R. Garey, SIAM J. Computing, 3 (June 1974), pp. 101-110.
  13. Performance Bounds on the Splitting Algorithm for Binary Testing, M. R. Garey and R. L. Graham, Acta Informatica, 3 (1974), pp. 347-355.
  14. Isolating a Single Defective Using Group Testing, M. R. Garey and F. K. Hwang, J. Amer. Statist. Assoc., 69 (March 1974), pp. 151-153.
  15. Worst Case Performance Bounds for Simple One-Dimensional Packing Algorithms, D. S. Johnson, M. R. Garey, R. L. Graham, A. Demers and J. D. Ullman, SIAM J. Computing, 3 (1974), pp. 299-325.
  16. On Cubical Graphs, M. R. Garey and R. L. Graham, J. Comb. Theory, 18 (February 1975), pp. 84-95.
  17. Bounds for Multiprocessor Scheduling With Resource Constraints, M. R. Garey and R. L. Graham, SIAM J. Computing, 4 (June 1975), pp. 187-200.
  18. Complexity Results for Multiprocessor Scheduling Under Resource Constraints, M. R. Garey and D. S. Johnson, SIAM J. Computing, 4 (1975), pp. 397-411.
  19. Efficient Generation of Optimal Prefix Codes-Equiprobable Words Using Unequal Cost Letters, M. R. Garey, Y. Perl and S. Even, J. Assoc. Comp. Mach., 22 (April 1975), pp. 202-214.
  20. Computational Aspects of Deciding if All Roots of a Polynomial Lie Within the Unit Circle, P. G. Anderson, M. R. Garey and L. E. Heindel, Computing, 16 (1976), pp. 293-304.
  21. On the Distance Matrix of a Tree, M. Edelberg, M. R. Garey and R. L. Graham, Discrete Math., 14 (1976), pp. 23-39.
  22. Some NP-Complete Geometric Problems, M. R. Garey, R. L. Graham and D. S. Johnson, Proc. 8th Annual ACM Symp. on Theory of Computing, 1976, pp. 10-22.
  23. Resource Constrained Scheduling as Generalized Bin Packing, M. R. Garey, R. L. Graham, D. S. Johnson and A. Yao, J. Comb. Theory A, 21 (1976), pp. 257-298.
  24. Approximation Algorithms for Combinatorial Problems: An Annotated Bibliography, M. R. Garey and D. S. Johnson, Algorithms and Complexity: New Directions and Recent Results, J. F. Traub (editor), Academic Press, 1976, pp. 41-52.
  25. The Complexity of Near Optimal Graph Coloring, M. R. Garey and D. S. Johnson, J. Assoc. Comp. Mach., 23 (1976), pp. 43-49.
  26. Scheduling Tasks with Non-Uniform Deadlines on Two Processors, M. R. Garey and D. S. Johnson, J. Assoc. Comp. Mach., 23 (1976), pp. 461-467.
  27. The Complexity of Flowshop and Jobshop Scheduling, M. R. Garey, D. S. Johnson and R. Sethi, Math. of Oper. Research, 1:2 (May 1976), pp. 117-129.
  28. An Application of Graph Coloring To Printed Circuit Testing, M. R. Garey, D. S. Johnson and H. C. So, IEEE Trans. on Circuits and Systems, CAS-23 (1976), pp. 591-599.
  29. Some Simplified NP-Complete Graph Problems, M. R. Garey, D. S. Johnson and L. Stockmeyer, Theoretical Comp. Sci., 1 (1976), pp. 237-267.
  30. The Planar Hamiltonian Circuit Problem is NP-Complete, M. R. Garey, D. S. Johnson and R. E. Tarjan, SIAM J. Computing, 5 (1976), pp. 704-714.
  31. Rectilinear Steiner Trees: Efficient Special Case Algorithms, A. V. Aho, M. R. Garey and F. K. Hwang, Networks, 7 (1977), pp. 37-58.
  32. Scheduling Equal-Length Tasks Under Treelike Precedence Constraints to Minimize Maximum Lateness, P. Brucker, M. R. Garey and D. S. Johnson, Math. of Oper. Research, 2 (1977), pp. 275-284.
  33. The Complexity of Computing Steiner Minimal Trees, M. R. Garey, R. L. Graham and D. S. Johnson, SIAM J. Appl. Math., 32 (1977), pp. 835-859.
  34. Algorithms for a Set Partitioning Problem Arising in the Design of Multi-Purpose Units, M. R. Garey, F. K. Hwang and D. S. Johnson, IEEE Trans. on Computers, C-26 (1977), pp. 321-328.
  35. The Rectilinear Steiner Tree Problem is NP-Complete, M. R. Garey and D. S. Johnson, SIAM J. Appl. Math., 32 (1977), pp. 826-834.
  36. Two-Processor Scheduling with Start-Times and Deadlines, M. R. Garey and D. S. Johnson, SIAM J. Computing, 6 (1977), pp. 416-426.
  37. A Note on Bisecting Minimum Spanning Trees, W. M. Boyce, M. R. Garey and D. S. Johnson, Networks, 8 (1978), pp. 187-192.
  38. Two Results Concerning Multicoloring, V. Chvatal, M. R. Garey and D. S. Johnson, Ann. Disc. Math., 2 (1978), pp. 151-154.
  39. An Application of Bin Packing to Multiprocessor Scheduling, E. G. Coffman, Jr., M. R. Garey and D. S. Johnson, SIAM J. Computing, 7 (1978), pp. 1-17.
  40. The Complexity of Checkers on an NxN Board: Preliminary Report, A. S. Fraenkel, M. R. Garey, D. S. Johnson, T. Schaefer and Y. Yesha, Proc. 19th Annual Symposium on Foundations of Computer Science, 1978, pp. 55-64.
  41. Limits to Computation, M. R. Garey and R. L. Graham, Encyclopedia Britannica, 1978 Yearbook of Science, 1978, pp. 170-185.
  42. On a Number Theoretic Bin Packing Conjecture, M. R. Garey, R. L. Graham and D. S. Johnson, Proc. 5th Hungarian Combinatorics Colloquium, 1978, pp. 377-399.
  43. Performance Guarantees for Scheduling Algorithms, M. R. Garey, R. L. Graham and D. S. Johnson, Operations Research, 26:1 (1978), pp. 3-21.
  44. Complexity Results for Bandwidth Minimization, M. R. Garey, R. L. Graham, D. S. Johnson and D. E. Knuth, SIAM J. Appl. Math., 34:3 (1978), pp. 477-495.
  45. A Note on "A Note on 'Some Simplified NP-Complete Graph Problems'", M. R. Garey and D. S. Johnson, SIGACT News, 9:4 (1978), page 17.
  46. Strong NP-Completeness Results: Motivation, Examples, and Implications, M. R. Garey and D. S. Johnson, J. Assoc. Comp. Mach., 25 (1978), pp. 499-508.
  47. Triangulating a Simple Polygon, M. R. Garey, D. S. Johnson, F. P. Preparata and R. E. Tarjan, Information Processing Letters, 7 (1978), pp. 175-179.
  48. A Linear-Time Algorithm for Finding All Feedback Vertices, M. R. Garey and R. E. Tarjan, Information Processing Letters, 7 (1978), pp. 274-276.
  49. Computers and Intractability: A Guide to the Theory of NP-Completeness, M. R. Garey and D. S. Johnson, W. H. Freeman, 1979.
  50. Performance Bounds for Level-Oriented Two Dimensional Packing Algorithms, E. G. Coffman, Jr., M. R. Garey, D. S. Johnson and R. E. Tarjan, SIAM J. Computing, 9 (1980), pp. 808-826.
  51. The Complexity of Coloring Circular Arcs and Chords, M. R. Garey, D. S. Johnson, G. L. Miller and C. H. Papadimitriou, SIAM J. Algebraic and Discrete Methods, 1 (1980), pp. 216-227.
  52. Scheduling Unit-Time Tasks with Arbitrary Release Times and Deadlines, M. R. Garey, D. S. Johnson, B. B. Simons and R. E. Tarjan, SIAM J. Computing, 10 (1981), pp. 256-269.
  53. Approximation Algorithms for Bin-Packing Problems: A Survey, M. R. Garey and D. S. Johnson, Analysis and Design of Algorithms in Combinatorial Optimization, G. Ausiello and M. Lucertini (editors), Springer-Verlag, New York, 1981, pp. 147-172.
  54. On Packing Two-Dimensional Bins, F. R. K. Chung, M. R. Garey and D. S. Johnson, SIAM J. Alg. and Disc. Methods, 3 (1982), pp. 66-76.
  55. The Complexity of the Generalized Lloyd-Max Problem, M. R. Garey, D. S. Johnson and H. S. Witsenhausen, IEEE Trans. on Information Theory, IT-28 (1982), pp. 255-256.
  56. Dynamic Bin Packing, E. G. Coffman, Jr., M. R. Garey and D. S. Johnson, SIAM J. Computing, 12 (1983), pp. 227-258.
  57. Scheduling Opposing Forests, M. R. Garey, D. S. Johnson, R. E. Tarjan and M. Yannakakis, SIAM J. Alg. and Disc. Methods, 4 (1983), pp. 72-93.
  58. Crossing Number is NP-complete, M. R. Garey and D. S. Johnson, SIAM J. on Algebraic and Discrete Methods, 4 (1983), pp. 312-316.
  59. Scheduling File Transfers, E. G. Coffman, Jr., M. R. Garey, D. S. Johnson and A. S. LaPaugh, SIAM J. Computing, 14 (1985), pp. 743-780, (Preliminary version published as: Scheduling File Transfers in a Distributed Network, Proceedings of the Second Annual ACM Symp. on Principles of Distributed Computing, 1983, pp. 254-266).
  60. Diameter Bounds for Altered Graphs, F. R. K. Chung and M. R. Garey, J. of Graph Theory, 8 (1984), pp. 511-534.
  61. A Stochastic Optimization Algorithm Minimizing Expected Flow Times on Uniform Processors, A. K. Agrawala, E. G. Coffman, Jr., M. R. Garey and S. K. Tripathi, IEEE Trans. on Computers, C-33:4 (1984), pp. 351-356.
  62. Approximation Algorithms for Bin Packing - An Updated Survey, E. G. Coffman, Jr., M. R. Garey and D. S. Johnson, Algorithm and Design for Computer System Design, G. Ausiello, M. Lucertini and P. Serafini (editors), Springer-Verlag, New York, 1984, pp. 49-106.
  63. Optimum Scan-Width Selection under Containment Constraints, M. R. Garey and R. Y. Pinter, AT&T Bell Laboratories Tech. J., 63 (1984), pp. 1191-1212.
  64. Composing Functions to Minimize Image Size, M. R. Garey and D. S. Johnson, SIAM J. Computing, 14 (1985), pp. 500-503.
  65. A 71/60 Theorem for Bin Packing, M. R. Garey and D. S. Johnson, Journal of Complexity, 1 (1985), pp. 65-106.
  66. Strongly Connected Orientations of Mixed Multigraphs, F. R. K. Chung, M. R. Garey and R. E. Tarjan, Networks, 15 (1985), pp. 477-484.
  67. Minimizing Expected Makespans on Uniform Processor Systems, E. G. Coffman, Jr., L. Flatto, M. R. Garey and R. R. Weber, Advances in Applied Probability, 19 (1987), pp. 177-201.
  68. One-Processor Scheduling with Symmetric Earliness and Tardiness Penalties, M. R. Garey, R. E. Tarjan and G. T. Wilfong, Math. of Operations Research, 13 (1988), pp. 330-348.
  69. Bin Packing with Divisible Item Sizes, E. G. Coffman, M. R. Garey and D. S. Johnson, J. Complexity, 3 (1987), pp. 406-428.
  70. Asymptotic Results for Partial Concentrators, M. R. Garey, F. K. Hwang and G. W. Richards, IEEE Trans. on Communications, 36 (1988), pp. 214-217.
  71. On the Fractional Covering Number of Hypergraphs, F. R. K. Chung, Z. F\*:uredi, M. R. Garey and R. L. Graham, SIAM J. Discrete Math., 1 (1988), pp. 45-49.
  72. The Complexity of Searching a Graph, N. Megiddo, S. L. Hakimi, M. R. Garey, D. S. Johnson and C. H. Papadimitriou, J. Assoc. Comp. Mach., 35 (1988), pp. 18-44, (A preliminary version appeared in : 22nd Ann. Symposium on Foundations of Computer Science, pp. 376-385, 1981)..
  73. Fundamental Discrepancies Between Average-Case Analyses Under Discrete and Continuous Distributions: A Bin Packing Case Study, E. G. Coffman, C. A. Courcoubetis, M. R. Garey, D. S. Johnson, L. A. McGeoch, P. W. Shor, R. R. Weber and M. Yannakakis, Proc. 23rd Annual ACM Symposium on Theory of Computing, 1991, pp. 230-240.
  74. Proof of the 4/3 Conjecture for Preemptive vs. Nonpreemptive Two-processor Scheduling, E. G. Coffman and M. R. Garey, J. Assoc. Comp. Mach., 40 (1993), pp. 991-1018.
  75. Approximation Algorithms for Bin Packing: A Survey, E. G. Coffman, M. R. Garey and D. S. Johnson, Approximation Algorithms for NP-Hard Problems, Dorit S. Hochbaum (editor), PWS Publishing Company, 1997, pp. 46-93.