M. R. Garey

According to our database, M. R. Garey authored at least 61 papers between 1972 and 2002.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2002

Perfect Packing Theorems and the Average-Case Behavior of Optimal and Online Bin Packing.

Edward G. Coffman Jr., Costas Courcoubetis, Michael R. Garey, David S. Johnson, Peter W. Shor, Richard R. Weber, Mihalis Yannakakis

SIAM Rev., 2002

2000

Bin Packing with Discrete Item Sizes, Part I: Perfect Packing Theorems and the Average Case Behavior of Optimal Packings.

Edward G. Coffman Jr., Costas Courcoubetis, M. R. Garey, David S. Johnson, Peter W. Shor, Richard R. Weber, Mihalis Yannakakis

SIAM J. Discret. Math., 2000

1993

Proof of the 4/3 Conjecture for Preemptive vs. Nonpreemptive Two-Processor Scheduling.

Edward G. Coffman Jr., M. R. Garey

J. ACM, 1993

1991

Fundamental Discrepancies between Average-Case Analyses under Discrete and Continuous Distributions: A Bin Packing Case Study

Edward G. Coffman Jr., Costas Courcoubetis, M. R. Garey, David S. Johnson, Lyle A. McGeoch, Peter W. Shor, Richard R. Weber, Mihalis Yannakakis

Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991

1989

The Complexity of Collapsing Reachability Graphs.

Sudhir Aggarwal, Daniel Barbará, Walter Cunto, M. R. Garey

Proceedings of the Automatic Verification Methods for Finite State Systems, 1989

1988

Asymptotic results for partial concentrators.

Michael R. Garey, Frank K. Hwang, Gaylord W. Richards

IEEE Trans. Commun., 1988

On the Fractional Covering Number of Hypergraphs.

Fan R. K. Chung, Zoltán Füredi, M. R. Garey, Ronald L. Graham

SIAM J. Discret. Math., 1988

One-Processor Scheduling with Symmetric Earliness and Tardiness Penalties.

Michael R. Garey, Robert E. Tarjan, Gordon T. Wilfong

Math. Oper. Res., 1988

The complexity of searching a graph.

Nimrod Megiddo, S. Louis Hakimi, M. R. Garey, David S. Johnson, Christos H. Papadimitriou

J. ACM, 1988

1987

Bin packing with divisible item sizes.

Edward G. Coffman Jr., M. R. Garey, David S. Johnson

J. Complex., 1987

1985

Composing Functions to Minimize Image Size.

M. R. Garey, David S. Johnson

SIAM J. Comput., 1985

Scheduling File Transfers.

Edward G. Coffman Jr., M. R. Garey, David S. Johnson, Andrea S. LaPaugh

SIAM J. Comput., 1985

Strongly connected orientations of mixed multigraphs.

Fan R. K. Chung, Michael R. Garey, Robert Endre Tarjan

Networks, 1985

A 71/60 theorem for bin packing.

David S. Johnson, M. R. Garey

J. Complex., 1985

1984

A Stochastic Optimization Algorithm Minimizing Expected Flow Times on Uniform Processors.

Ashok K. Agrawala, Edward G. Coffman Jr., M. R. Garey, Satish K. Tripathi

IEEE Trans. Computers, 1984

Diameter bounds for altered graphs.

F. R. K. Chung, M. R. Garey

J. Graph Theory, 1984

Optimum scan-width selection under containment constraints.

Michael R. Garey, Ron Y. Pinter

AT&T Bell Lab. Tech. J., 1984

1983

Dynamic Bin Packing.

Edward G. Coffman Jr., M. R. Garey, David S. Johnson

SIAM J. Comput., 1983

Scheduling File Transfers in a Distributed Network.

Edward G. Coffman Jr., M. R. Garey, David S. Johnson, Andrea S. LaPaugh

Proceedings of the Second Annual ACM Symposium on Principles of Distributed Computing, 1983

1982

The complexity of the generalized Lloyd - Max problem.

M. R. Garey, David S. Johnson, Hans S. Witsenhausen

IEEE Trans. Inf. Theory, 1982

1981

Scheduling Unit-Time Tasks with Arbitrary Release Times and Deadlines.

M. R. Garey, David S. Johnson, Barbara B. Simons, Robert Endre Tarjan

SIAM J. Comput., 1981

The Complexity of Searching a Graph (Preliminary Version)

Nimrod Megiddo, S. Louis Hakimi, M. R. Garey, David S. Johnson, Christos H. Papadimitriou

Proceedings of the 22nd Annual Symposium on Foundations of Computer Science, 1981

1980

The Complexity of Coloring Circular Arcs and Chords.

M. R. Garey, David S. Johnson, Gerald L. Miller, Christos H. Papadimitriou

SIAM J. Algebraic Discret. Methods, 1980

Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms.

Edward G. Coffman Jr., M. R. Garey, David S. Johnson, Robert Endre Tarjan

SIAM J. Comput., 1980

1979

Computers and Intractability: A Guide to the Theory of NP-Completeness.

M. R. Garey, David S. Johnson

W. H. Freeman, ISBN: 0-7167-1044-7, 1979

1978

A note on "A note on 'Some simplified NP-complete graph problems'".

Michael R. Garey, David S. Johnson

SIGACT News, 1978

An Application of Bin-Packing to Multiprocessor Scheduling.

Edward G. Coffman Jr., M. R. Garey, David S. Johnson

SIAM J. Comput., 1978

A note on bisecting minimum spanning trees.

William M. Boyce, M. R. Garey, David S. Johnson

Networks, 1978

"Strong" NP-Completeness Results: Motivation, Examples, and Implications.

M. R. Garey, David S. Johnson

J. ACM, 1978

A Linear-Time Algorithm for Finding All Feedback Vertices.

M. R. Garey, Robert Endre Tarjan

Inf. Process. Lett., 1978

Triangulating a Simple Polygon.

M. R. Garey, David S. Johnson, Franco P. Preparata, Robert Endre Tarjan

Inf. Process. Lett., 1978

Performance Guarantees for Scheduling Algorithms.

M. R. Garey, Ronald L. Graham, David S. Johnson

Oper. Res., 1978

The Complexity of Checkers on an N * N Board - Preliminary Report

Aviezri S. Fraenkel, M. R. Garey, David S. Johnson, T. Schaefer, Yaacov Yesha

Proceedings of the 19th Annual Symposium on Foundations of Computer Science, 1978

1977

Algorithms for a Set Partitioning Problem Arising in the Design of Multipurpose Units.

M. R. Garey, Frank K. Hwang, David S. Johnson

IEEE Trans. Computers, 1977

Two-Processor Scheduling with Start-Times and Deadlines.

M. R. Garey, David S. Johnson

SIAM J. Comput., 1977

The Rectilinear Steiner Tree Problem is NP Complete.

M. R. Garey, David S. Johnson

SIAM Journal of Applied Mathematics, 1977

Rectilinear steiner trees: Efficient special-case algorithms.

Alfred V. Aho, Michael R. Garey, Frank K. Hwang

Networks, 1977

Scheduling Equal-Length Tasks Under Treelike Precedence Constraints to Minimize Maximum Lateness.

Peter Brucker, Michael R. Garey, David S. Johnson

Math. Oper. Res., 1977

1976

Some Simplified NP-Complete Graph Problems.

M. R. Garey, David S. Johnson, Larry J. Stockmeyer

Theor. Comput. Sci., 1976

The Planar Hamiltonian Circuit Problem is NP-Complete.

M. R. Garey, David S. Johnson, Robert Endre Tarjan

SIAM J. Comput., 1976

The Complexity of Flowshop and Jobshop Scheduling.

Michael R. Garey, David S. Johnson, Ravi Sethi

Math. Oper. Res., 1976

Resource Constrained Scheduling as Generalized Bin Packing.

M. R. Garey, Ronald L. Graham, David S. Johnson, Andrew Chi-Chih Yao

J. Comb. Theory A, 1976

Scheduling Tasks with Nonuniform Deadlines on Two Processors.

M. R. Garey, David S. Johnson

J. ACM, 1976

The Complexity of Near-Optimal Graph Coloring.

M. R. Garey, David S. Johnson

J. ACM, 1976

On the distance matrix of a tree.

M. Edelberg, M. R. Garey, Ronald L. Graham

Discret. Math., 1976

Computational aspects of deciding if all roots of a polynomial lie within the unit circle.

Peter Gordon Anderson, M. R. Garey, Lee E. Heindel

Computing, 1976

Some NP-Complete Geometric Problems

M. R. Garey, Ronald L. Graham, David S. Johnson

Proceedings of the 8th Annual ACM Symposium on Theory of Computing, 1976

1975

Complexity Results for Multiprocessor Scheduling under Resource Constraints.

M. R. Garey, David S. Johnson

SIAM J. Comput., 1975

Bounds for Multiprocessor Scheduling with Resource Constraints.

M. R. Garey, Ronald L. Graham

SIAM J. Comput., 1975

Efficient Generation of Optimal Prefix Code: Equiprobable Words Using Unequal Cost Letters.

Yehoshua Perl, M. R. Garey, Shimon Even

J. ACM, 1975

An Application of Graph Coloring to Printed Circuit Testing (Working Paper)

M. R. Garey, David S. Johnson, H. C. So

Proceedings of the 16th Annual Symposium on Foundations of Computer Science, 1975

1974

Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms.

David S. Johnson, Alan J. Demers, Jeffrey D. Ullman, M. R. Garey, Ronald L. Graham

SIAM J. Comput., 1974

Optimal Binary Search Trees with Restricted Maximal Depth.

M. R. Garey

SIAM J. Comput., 1974

Performance Bounds on the Splitting Algorithm for Binary Testing.

M. R. Garey, Ronald L. Graham

Acta Informatica, 1974

Some Simplified NP-Complete Problems

M. R. Garey, David S. Johnson, Larry J. Stockmeyer

Proceedings of the 6th Annual ACM Symposium on Theory of Computing, April 30, 1974

1973

Optimal task sequencing with precedence constraints.

M. R. Garey

Discret. Math., 1973

Bounds on Scheduling with Limited Resources.

M. R. Garey, Ronald L. Graham

Proceedings of the Fourth Symposium on Operating System Principles, 1973

1972

Simple Binary Identification Problems.

Michael Randolph Garey

IEEE Trans. Computers, 1972

Resident-Bubble Cellular Logic Using Magnetic Domains.

Michael Randolph Garey

IEEE Trans. Computers, 1972

The Transitive Reduction of a Directed Graph.

Alfred V. Aho, M. R. Garey, Jeffrey D. Ullman

SIAM J. Comput., 1972

Worst-Case Analysis of Memory Allocation Algorithms

M. R. Garey, Ronald L. Graham, Jeffrey D. Ullman

Proceedings of the 4th Annual ACM Symposium on Theory of Computing, 1972