Lyle A. McGeoch

SODA Conference 1996 Conference Paper

Asymptotic Experimental Analysis for the Held-Karp Traveling Salesman Bound

• David S. Johnson 0001
• Lyle A. McGeoch
• Edward E. Rothberg

SODA Conference 1993 Conference Paper

Data Structures for Traveling Salesmen

• Michael L. Fredman
• David S. Johnson 0001
• Lyle A. McGeoch
• G. Ostheimer

STOC Conference 1991 Conference Paper

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 0001
• Lyle A. McGeoch
• Peter W. Shor
• Richard R. Weber 0003
• Mihalis Yannakakis

SODA Conference 1990 Conference Paper

Competitive Randomized Algorithms for Non-Uniform Problems

• Anna R. Karlin
• Mark S. Manasse
• Lyle A. McGeoch
• Susan S. Owicki

STOC Conference 1988 Conference Paper

Competitive Algorithms for On-line Problems

• Mark S. Manasse
• Lyle A. McGeoch
• Daniel Dominic Sleator

An on-line problem is one in which an algorithm must handle a sequence of requests, satisfying each request without knowledge of the future requests. Examples of on-line problems include scheduling the motion of elevators, finding routes in networks, allocating cache memory, and maintaining dynamic data structures. A competitive algorithm for an on-line problem has the property that its performance on any sequence of requests is within a constant factor of the performance of any other algorithm on the same sequence. This paper presents several general results concerning competitive algorithms, as well as results on specific on-line problems.

STOC Conference 1984 Conference Paper

Some Unexpected Expected Behavior Results for Bin Packing

• Jon Louis Bentley
• David S. Johnson 0001
• Frank Thomson Leighton
• Catherine C. McGeoch
• Lyle A. McGeoch