## George S. Lueker

Professor

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

Email: lueker@ics.uci.edu

University of California, Irvine

CS 358A

Mail Code: 3425

Irvine, CA 92697

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

Email: lueker@ics.uci.edu

University of California, Irvine

CS 358A

Mail Code: 3425

Irvine, CA 92697

**Research Interests**

Algorithms and Data Structures, Probabilistic Analysis

**URL**

**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.

Publications

``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.

**Link to this profile**

**Last updated**

10/21/2004