M. R. Garey

  • Bell Labs

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

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.


ACM Fellow

ACM Fellow 1995, "For fundamental contributions to the theory of complexity and algorithms and for outstanding service to ACM.".



In proceedings 
PhD thesis 


Online presence:

On csauthors.net:


Perfect Packing Theorems and the Average-Case Behavior of Optimal and Online Bin Packing.
SIAM Rev., 2002

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

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

Fundamental Discrepancies between Average-Case Analyses under Discrete and Continuous Distributions: A Bin Packing Case Study
Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991

The Complexity of Collapsing Reachability Graphs.
Proceedings of the Automatic Verification Methods for Finite State Systems, 1989

Asymptotic results for partial concentrators.
IEEE Trans. Commun., 1988

On the Fractional Covering Number of Hypergraphs.
SIAM J. Discret. Math., 1988

One-Processor Scheduling with Symmetric Earliness and Tardiness Penalties.
Math. Oper. Res., 1988

The complexity of searching a graph.
J. ACM, 1988

Bin packing with divisible item sizes.
J. Complex., 1987

Composing Functions to Minimize Image Size.
SIAM J. Comput., 1985

Scheduling File Transfers.
SIAM J. Comput., 1985

Strongly connected orientations of mixed multigraphs.
Networks, 1985

A 71/60 theorem for bin packing.
J. Complex., 1985

A Stochastic Optimization Algorithm Minimizing Expected Flow Times on Uniform Processors.
IEEE Trans. Computers, 1984

Diameter bounds for altered graphs.
J. Graph Theory, 1984

Optimum scan-width selection under containment constraints.
AT&T Bell Lab. Tech. J., 1984

Dynamic Bin Packing.
SIAM J. Comput., 1983

Scheduling File Transfers in a Distributed Network.
Proceedings of the Second Annual ACM Symposium on Principles of Distributed Computing, 1983

The complexity of the generalized Lloyd - Max problem.
IEEE Trans. Inf. Theory, 1982

Scheduling Unit-Time Tasks with Arbitrary Release Times and Deadlines.
SIAM J. Comput., 1981

The Complexity of Searching a Graph (Preliminary Version)
Proceedings of the 22nd Annual Symposium on Foundations of Computer Science, 1981

The Complexity of Coloring Circular Arcs and Chords.
SIAM J. Algebraic Discret. Methods, 1980

Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms.
SIAM J. Comput., 1980

Computers and Intractability: A Guide to the Theory of NP-Completeness.
W. H. Freeman, ISBN: 0-7167-1044-7, 1979

A note on "A note on 'Some simplified NP-complete graph problems'".
SIGACT News, 1978

An Application of Bin-Packing to Multiprocessor Scheduling.
SIAM J. Comput., 1978

A note on bisecting minimum spanning trees.
Networks, 1978

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

A Linear-Time Algorithm for Finding All Feedback Vertices.
Inf. Process. Lett., 1978

Triangulating a Simple Polygon.
Inf. Process. Lett., 1978

Performance Guarantees for Scheduling Algorithms.
Oper. Res., 1978

The Complexity of Checkers on an N * N Board - Preliminary Report
Proceedings of the 19th Annual Symposium on Foundations of Computer Science, 1978

Algorithms for a Set Partitioning Problem Arising in the Design of Multipurpose Units.
IEEE Trans. Computers, 1977

Two-Processor Scheduling with Start-Times and Deadlines.
SIAM J. Comput., 1977

The Rectilinear Steiner Tree Problem is NP Complete.
SIAM Journal of Applied Mathematics, 1977

Rectilinear steiner trees: Efficient special-case algorithms.
Networks, 1977

Scheduling Equal-Length Tasks Under Treelike Precedence Constraints to Minimize Maximum Lateness.
Math. Oper. Res., 1977

Some Simplified NP-Complete Graph Problems.
Theor. Comput. Sci., 1976

The Planar Hamiltonian Circuit Problem is NP-Complete.
SIAM J. Comput., 1976

The Complexity of Flowshop and Jobshop Scheduling.
Math. Oper. Res., 1976

Resource Constrained Scheduling as Generalized Bin Packing.
J. Comb. Theory, Ser. A, 1976

Scheduling Tasks with Nonuniform Deadlines on Two Processors.
J. ACM, 1976

The Complexity of Near-Optimal Graph Coloring.
J. ACM, 1976

On the distance matrix of a tree.
Discret. Math., 1976

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

Some NP-Complete Geometric Problems
Proceedings of the 8th Annual ACM Symposium on Theory of Computing, 1976

Complexity Results for Multiprocessor Scheduling under Resource Constraints.
SIAM J. Comput., 1975

Bounds for Multiprocessor Scheduling with Resource Constraints.
SIAM J. Comput., 1975

Efficient Generation of Optimal Prefix Code: Equiprobable Words Using Unequal Cost Letters.
J. ACM, 1975

An Application of Graph Coloring to Printed Circuit Testing (Working Paper)
Proceedings of the 16th Annual Symposium on Foundations of Computer Science, 1975

Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms.
SIAM J. Comput., 1974

Optimal Binary Search Trees with Restricted Maximal Depth.
SIAM J. Comput., 1974

Performance Bounds on the Splitting Algorithm for Binary Testing.
Acta Informatica, 1974

Some Simplified NP-Complete Problems
Proceedings of the 6th Annual ACM Symposium on Theory of Computing, April 30, 1974

Optimal task sequencing with precedence constraints.
Discret. Math., 1973

Bounds on Scheduling with Limited Resources.
Proceedings of the Fourth Symposium on Operating System Principles, 1973

Simple Binary Identification Problems.
IEEE Trans. Computers, 1972

Resident-Bubble Cellular Logic Using Magnetic Domains.
IEEE Trans. Computers, 1972

The Transitive Reduction of a Directed Graph.
SIAM J. Comput., 1972

Worst-Case Analysis of Memory Allocation Algorithms
Proceedings of the 4th Annual ACM Symposium on Theory of Computing, 1972