DIMACS TR: 94-34
Upper and Lower Bounds for Selection on the Mesh
Authors: Anne Condon and Lata Narayanan
A distance-optimal algorithm for selection on the mesh has proved to be
elusive, although distance-optimal algorithms for the related problems of
routing and sorting have recently been discovered. In this paper, we explain,
using the notion of _adaptiveness, why techniques used in the currently best
selection algorithms cannot lead to a distance-optimal algorithm.
For worst-case inputs, we apply new techniques to improve the previous best
upper bound of 1.22n of Kaklamanis et al. to 1.15n. This improvement is
obtained in part by increasing the adaptiveness of previous algorithms. We
also present the first algorithm for selection that has distance-optimal
performance on average.
Paper available at:
DIMACS Home Page