Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 18 Novembre 2003

Adaptive Sampling for Quickselect

par Alfredo Viola (Université de Montevideo, Uruguay)

The median-of-3 variant of quickselect has been largely 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.

The talk will be concentrated in the algorithmic aspects of the problem, as well as how its analysis contributes to the understanding of the most delicate parts of them.

This is a joint work with Conrado Martinez and Daniel Panario.

Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30