George S. Lueker

Donald Bren School of Information and Computer Sciences

PH.D., Princeton University, 1975
M.A., Princeton University 1973

Phone: (949) 824-5866
Fax: (949) 824-4056

University of California, Irvine
CS 358A
Mail Code: 3425
Irvine, CA 92697
Research Interests
Algorithms and Data Structures, Probabilistic Analysis
Research Abstract
George Lueker's interests are in the area of the design and analysis of algorithms for concrete problems. Lueker is especially interested in applications of probability to problems in computer science, in particular the analysis of the behavior of algorithms and optimization problems when some assumption is made about the probability distribution of inputs. For example, he has investigated the behavior of the optimum solution to the bin-packing problem and the partition problem. Also, with graduate student Molodowitch he developed a remarkably simple proof of the result that the probabilistic behavior of double hashing is asymptotically equivalent to that of the theoretically ideal uniform hashing, even for large load factors. He is presently especially interested in the behavior of the longest common subsequence problem when the input strings are random.
``Improved Bounds on the Average Length of Longest Common Subsequences," Fourteenth Annual ACM/SIAM Symposium on Discrete Algorithms, 2003, pp. 130-131.
`The Minimum Expectation Selection Problem,'' with David Eppstein, Random Structures & Algorithms, 21 (2002), pp. 278-292.
"Packing Random Rectangles," with E. G. Coffman, Jr., Joel Spencer, and Peter M. Winkler, Probability Theory and Related Fields 120 (2001), pp. 585-599.
"Approximation Algorithms for Extensible Bin Packing," with E. G. Coffman, Proc. Twelfth Annual ACM/SIAM Symposium on Discrete Algorithms (2001), pp. 586-588.
"Average-Case Analysis of Off-Line and On-Line Knapsack Problems," Journal of Algorithms 29 (1998), pp. 277-305.
"Exponentially Small Bounds on the Expected Optimum of the Partition and Subset Sum Problems," Random Structures and Algorithms 12 (1998), pp. 51-62.

"More Analysis of Double Hashing," with M. Molodowitch, Combinatorica 13,1 (1993), pp. 83-96.

Last updated