TITLE: Adaptive Sampling for Quickselect
SPEAKER:
Prof. Alfredo Viola
Computer Science Institute
University of Uruguay
TIME: 2:00 - 3:00 P.M., Friday June 11, 2004
LOCATION: Pi, 1 L (PA)
HOST: Gadiel Seroussi
ABSTRACT:
The median-of-3 variant of quickselect has been widely studied. However, the
following natural adaptive variant had not been analyzed: ``choose as pivot the
smallest of the sample if the rank of the sought element is small, the largest
if the rank is large, and the median if the rank is medium''. We first analyze
proportional-of-2 and proportional-of-3 in which we use equal-size intervals. We
propose $\nu$-find, a generalization of median-of-3 and proportional-of-3 with
interval breakpoints $\nu$ and $1-\nu$. We give the optimal $\nu$ and values for
which $\nu$-find outperforms median-of-3. We also present general results for
larger sample sizes. Our strategies are optimal in the sense that for sampling
sizes growing to infinity, we achieve the lower bound for selection.
The talk will focus on the algorithmic aspects of the problem, as well as how
its analysis contributes to the understanding of some intricate aspects of their
performance.
This is a joint work with Conrado Mart\'{\i}nez and Daniel Panario.
|
printable version
