The minimum expectation selection problem

David Eppstein
and George S. Lueker

*Random Structures & Algorithms* 21(3–4):278–292, 2002

*Mathematical Reviews* 2003m:68054, 2003

Reviewed by Marc Ulrich Stiller

The authors discuss the min-min expectation selection problem (and variations): selecting $k$ out of $n$ given discrete probability distributions, to minimize the expectation of the minimum value resulting when independent random variables are drawn from the selected distributions. They show NP-completeness (with a fully polynomial time approximation scheme), if the number of distinct values in each distribution is a constant greater than 2, and NP-hardness to approximate the problem within any constant approximation factor, if that number is an arbitrary integer. Finally they show that the related max-min problem (maximize the expectation) is polynomially solvable for a constant number of values in each distribution. The article is a very interesting example of demonstrating the interplay of probability theory and computer science. The reader should be familiar with the concepts of NP-theory, including the issue of approximation algorithms for such problems.