M. R. Garey

Publication Activity (10 Years)

Years Active: 1972-2000
Publications (10 Years): 0

Publications

Edward G. Coffman Jr., Costas Courcoubetis, M. R. Garey, David S. Johnson, Peter W. Shor, Richard R. Weber, Mihalis Yannakakis
Bin Packing with Discrete Item Sizes, Part I: Perfect Packing Theorems and the Average Case Behavior of Optimal Packings. SIAM J. Discret. Math. 13 (3) (2000)
Edward G. Coffman Jr., M. R. Garey
Proof of the 4/3 Conjecture for Preemptive vs. Nonpreemptive Two-Processor Scheduling. J. ACM 40 (5) (1993)
Edward G. Coffman Jr., Costas Courcoubetis, M. R. Garey, David S. Johnson, Lyle A. McGeoch, Peter W. Shor, Richard R. Weber, Mihalis Yannakakis
Fundamental Discrepancies between Average-Case Analyses under Discrete and Continuous Distributions: A Bin Packing Case Study STOC (1991)
Edward G. Coffman Jr., M. R. Garey
Proof of the 4/3 Conjecture for Preemptive vs. Nonpreemptive Two-Processor Scheduling STOC (1991)
Sudhir Aggarwal, Daniel Barbará, Walter Cunto, M. R. Garey
The Complexity of Collapsing Reachability Graphs. Automatic Verification Methods for Finite State Systems (1989)
Nimrod Megiddo, S. Louis Hakimi, M. R. Garey, David S. Johnson, Christos H. Papadimitriou
The complexity of searching a graph. J. ACM 35 (1) (1988)
Fan R. K. Chung, Zoltán Füredi, M. R. Garey, Ronald L. Graham
On the Fractional Covering Number of Hypergraphs. SIAM J. Discret. Math. 1 (1) (1988)
Edward G. Coffman Jr., M. R. Garey, David S. Johnson
Bin packing with divisible item sizes. J. Complex. 3 (4) (1987)
Edward G. Coffman Jr., M. R. Garey, David S. Johnson, Andrea S. LaPaugh
Scheduling File Transfers. SIAM J. Comput. 14 (3) (1985)
David S. Johnson, M. R. Garey
A 71/60 theorem for bin packing. J. Complex. 1 (1) (1985)
M. R. Garey, David S. Johnson
Composing Functions to Minimize Image Size. SIAM J. Comput. 14 (2) (1985)
F. R. K. Chung, M. R. Garey
Diameter bounds for altered graphs. J. Graph Theory 8 (4) (1984)
Ashok K. Agrawala, Edward G. Coffman Jr., M. R. Garey, Satish K. Tripathi
A Stochastic Optimization Algorithm Minimizing Expected Flow Times on Uniform Processors. IEEE Trans. Computers 33 (4) (1984)
Edward G. Coffman Jr., M. R. Garey, David S. Johnson, Andrea S. LaPaugh
Scheduling File Transfers in a Distributed Network. PODC (1983)
Edward G. Coffman Jr., M. R. Garey, David S. Johnson
Dynamic Bin Packing. SIAM J. Comput. 12 (2) (1983)
M. R. Garey, David S. Johnson, Hans S. Witsenhausen
The complexity of the generalized Lloyd - Max problem. IEEE Trans. Inf. Theory 28 (2) (1982)
M. R. Garey, David S. Johnson, Barbara B. Simons, Robert Endre Tarjan
Scheduling Unit-Time Tasks with Arbitrary Release Times and Deadlines. SIAM J. Comput. 10 (2) (1981)
Nimrod Megiddo, S. Louis Hakimi, M. R. Garey, David S. Johnson, Christos H. Papadimitriou
The Complexity of Searching a Graph (Preliminary Version) FOCS (1981)
Edward G. Coffman Jr., M. R. Garey, David S. Johnson, Robert Endre Tarjan
Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms. SIAM J. Comput. 9 (4) (1980)
M. R. Garey, David S. Johnson, G. L. Miller, Christos H. Papadimitriou
The Complexity of Coloring Circular Arcs and Chords. SIAM J. Algebraic Discret. Methods 1 (2) (1980)
Aviezri S. Fraenkel, M. R. Garey, David S. Johnson, T. Schaefer, Yaacov Yesha
The Complexity of Checkers on an N * N Board - Preliminary Report FOCS (1978)
M. R. Garey, David S. Johnson
"Strong" NP-Completeness Results: Motivation, Examples, and Implications. J. ACM 25 (3) (1978)
M. R. Garey, Robert Endre Tarjan
A Linear-Time Algorithm for Finding All Feedback Vertices. Inf. Process. Lett. 7 (6) (1978)
William M. Boyce, M. R. Garey, David S. Johnson
A note on bisecting minimum spanning trees. Networks 8 (3) (1978)
M. R. Garey, Ronald L. Graham, David S. Johnson
Performance Guarantees for Scheduling Algorithms. Oper. Res. 26 (1) (1978)
Edward G. Coffman Jr., M. R. Garey, David S. Johnson
An Application of Bin-Packing to Multiprocessor Scheduling. SIAM J. Comput. 7 (1) (1978)
M. R. Garey, David S. Johnson, Franco P. Preparata, Robert Endre Tarjan
Triangulating a Simple Polygon. Inf. Process. Lett. 7 (4) (1978)
M. R. Garey, Frank K. Hwang, David S. Johnson
Algorithms for a Set Partitioning Problem Arising in the Design of Multipurpose Units. IEEE Trans. Computers 26 (4) (1977)
M. R. Garey, David S. Johnson
The Rectilinear Steiner Tree Problem in NP Complete. SIAM Journal of Applied Mathematics 32 (1977)
M. R. Garey, David S. Johnson
Two-Processor Scheduling with Start-Times and Deadlines. SIAM J. Comput. 6 (3) (1977)
M. R. Garey, David S. Johnson
The Complexity of Near-Optimal Graph Coloring. J. ACM 23 (1) (1976)
M. R. Garey, Ronald L. Graham, David S. Johnson
Some NP-Complete Geometric Problems STOC (1976)
M. R. Garey, Ronald L. Graham, David S. Johnson, Andrew Chi-Chih Yao
Resource Constrained Scheduling as Generalized Bin Packing. J. Comb. Theory, Ser. A 21 (3) (1976)
M. R. Garey, David S. Johnson
Scheduling Tasks with Nonuniform Deadlines on Two Processors. J. ACM 23 (3) (1976)
M. R. Garey, David S. Johnson, Larry J. Stockmeyer
Some Simplified NP-Complete Graph Problems. Theor. Comput. Sci. 1 (3) (1976)
P. G. Anderson, M. R. Garey, Lee E. Heindel
Computational aspects of deciding if all roots of a polynomial lie within the unit circle. Computing 16 (4) (1976)
M. Edelberg, M. R. Garey, Ronald L. Graham
On the distance matrix of a tree. Discret. Math. 14 (1) (1976)
M. R. Garey, David S. Johnson, Robert Endre Tarjan
The Planar Hamiltonian Circuit Problem is NP-Complete. SIAM J. Comput. 5 (4) (1976)
Yehoshua Perl, M. R. Garey, Shimon Even
Efficient Generation of Optimal Prefix Code: Equiprobable Words Using Unequal Cost Letters. J. ACM 22 (2) (1975)
M. R. Garey, David S. Johnson, H. C. So
An Application of Graph Coloring to Printed Circuit Testing (Working Paper) FOCS (1975)
M. R. Garey, Ronald L. Graham
Bounds for Multiprocessor Scheduling with Resource Constraints. SIAM J. Comput. 4 (2) (1975)
M. R. Garey, David S. Johnson
Complexity Results for Multiprocessor Scheduling under Resource Constraints. SIAM J. Comput. 4 (4) (1975)
M. R. Garey, David S. Johnson, Larry J. Stockmeyer
Some Simplified NP-Complete Problems STOC (1974)
M. R. Garey
Optimal Binary Search Trees with Restricted Maximal Depth. SIAM J. Comput. 3 (2) (1974)
David S. Johnson, Alan J. Demers, Jeffrey D. Ullman, M. R. Garey, Ronald L. Graham
Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms. SIAM J. Comput. 3 (4) (1974)
M. R. Garey, Ronald L. Graham
Performance Bounds on the Splitting Algorithm for Binary Testing. Acta Informatica 3 (1974)
M. R. Garey, Ronald L. Graham
Bounds on Scheduling with Limited Resources. SOSP (1973)
M. R. Garey
Optimal task sequencing with precedence constraints. Discret. Math. 4 (1) (1973)
Alfred V. Aho, M. R. Garey, Jeffrey D. Ullman
The Transitive Reduction of a Directed Graph. SIAM J. Comput. 1 (2) (1972)
M. R. Garey, Ronald L. Graham, Jeffrey D. Ullman
Worst-Case Analysis of Memory Allocation Algorithms STOC (1972)