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

Course Offerings | Research | Selected Publications

Electronic mail:

    To construct my electronic mail address, concatenate my last name and "@ics.uci.edu".

Spring 2008 Course Offerings

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

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.

``Improved Bounds on the Average Length of Longest Common Subsequences," Fourteenth Annual ACM/SIAM Symposium on Discrete Algorithms, 2003, pp. 130-131. Extended version.

``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," presented at the 2008 Workshop on Analytic Algorithmics and Combinatorics (ANALCO08), January 2008.

Course Offerings | Research | Publications
Department of Computer Science
School of Information and Computer Science
University of California, Irvine CA 92697-3435

Last modified