George S. Lueker
Position: Professor Emeritus
Area: Theory
Office: Bren Hall 4206
(949) 824-5866

Research | Selected Publications

Electronic mail:

    To construct my electronic mail address, concatenate my last name and "".

Research Interests

    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. With graduate student Mariko 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, for fixed load factors arbitrarily close to one. He has also investigated improved bounds on the expected length of the longest common subsequence when the input strings are random.

Selected Publications:

``Bin Packing Can Be Solved within 1+ε in Linear Time,'' with W. Fernandez de la Vega, Combinatorica 1,4, pp. 349-355, 1981.

``Probabilistic Analysis of Optimum Partitioning,'' with N. Karmarkar, R. M. Karp, and A. M. Odlyzko, Journal of Applied Probability 23,3 (1986), pp. 626-645.

Probabilistic Analysis of Packing and Partitioning Algorithms, with Ed Coffman, Jr., Wiley Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, 1991, 192 pages.

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

``Exponentially Small Bounds on the Expected Optimum of the Partition and Subset Sum Problems,'' Random Structures and Algorithms 12 (1998), pp. 51-62.

``Average-Case Analysis of Off-Line and On-Line Knapsack Problems,'' Journal of Algorithms 29 (1998), pp. 277-305.

``Packing Random Rectangles,'' with E. G. Coffman, Jr., Joel Spencer, and Peter M. Winkler, Probability Theory and Related Fields 120 (2001), pp. 585-599. An earlier version appeared as DIMACS TR 99-44.

``The Minimum Expectation Selection Problem,'' with David Eppstein. Presented at Random Structures and Algorithms 2001 held in Poznan, Poland. ACM Computing Research Repository, cs.DS/0110011. Random Structures & Algorithms, 21 (2002), pp. 278-292.

``C-Planarity of Extrovert Clustered Graphs,'' with Michael T. Goodrich and Jonathan Z. Sun, Lecture Notes in Computer Science, Vol. 3843, 2006, pp. 211-222. (Graph Drawing, 13th International Symposium, Patrick Healy and Nikola S. Nikolov, eds., Limerick, Ireland, September 12-14, 2005.)

``Approximation Algorithms for Extensible Bin Packing,'' with E. G. Coffman, Journal of Scheduling 9,1 (2006). An earlier version appeared in Proc. Twelfth Annual ACM/SIAM Symposium on Discrete Algorithms, 2001, pp. 586-588.

``On the Convergence of Upper Bound Techniques for the Average Length of Longest Common Subsequences," Proceedings of the Tenth Workshop on Algorithm Engineering and Experiments (ALENEX) and the Fifth Workshop on Analytic Algorithmics and Combinatorics (ANALCO), (January 19, 2008), pp. 169-182.

``On the Approximability of Geometric and Geographic Generalization and the Min-Max Bin Covering Problem," with Wenliang Du, David Eppstein, and Michael T. Goodrich, Algorithms and Data Structures Symposium (WADS 2009).

``Improved Bounds on the Average Length of Longest Common Subsequences," Journal of the ACM 56,3 (May 2009), Article 17, 38 pages. This is based on the paper of the same title in the Fourteenth Annual ACM/SIAM Symposium on Discrete Algorithms, 2003, pp. 130-131, and the ANALCO paper "On the Convergence of Upper Bound Techniques for the Average Length of Longest Common Subsequences" listed above.

Research | Publications

Department of Computer Science
School of Information and Computer Science
University of California, Irvine
Irvine, CA  92697-3435

Last modified