Publications with George Lueker
Fast optimal parallel algorithms for maximal matching in sparse graphs.
H. Asuri, M. Dillencourt, D. Eppstein, G. Lueker, and M. Molodowitch.
Tech. Rep. 92-01, ICS, UCI, 1992.We later discovered that the same results were published in a SPAA paper by Greg Shannon.
The minimum expectation selection problem.
D. Eppstein and G. Lueker.
10th Int. Conf. Random Structures and Algorithms, Poznan, Poland, August 2001.
arXiv:cs.DS/0110011.
Random Structures and Algorithms 21: 278–292, 2002.We define the min-min expectation selection problem (resp. max-min expectation selection problem) to be that of selecting k out of n given discrete probability distributions, to minimize (resp. maximize) the expectation of the minimum value resulting when independent random variables are drawn from the selected distributions. Such problems can be viewed as a simple form of two-stage stochastic programming. We show that if d, the number of values in the support of the distributions, is a constant greater than 2, the min-min expectation problem is NP-complete but admits a fully polynomial time approximation scheme. For d an arbitrary integer, it is NP-hard to approximate the min-min expectation problem with any constant approximation factor. The max-min expectation problem is polynomially solvable for constant d; we leave open its complexity for variable d. We also show similar results for binary selection problems in which we must choose one distribution from each of n pairs of distributions.
On the approximability of geometric and geographic generalization and the min-max bin covering problem.
W. Du, D. Eppstein, M. T. Goodrich, G. Lueker.
arXiv:0904.3756.
Algorithms and Data Structures Symposium (WADS), Banff, Canada.
Springer, Lecture Notes in Comp. Sci. 5664, 2009, pp. 242–253.We investigate several simplified models for k-anonymization in databases, show them to be hard to solve exactly, and provide approximation algorithms for them.
The min-max bin covering problem is closely related to one of our models. An input to this problem consists of a collection of items with sizes and a threshold size. The items must be grouped into bins such that the total size within each bin is at least the threshold, while keeping the maximum bin size as small as possible.