Upper and Lower Bounds for Selection on the Mesh |
| |
Authors: | A. Condon L. Narayanan |
| |
Affiliation: | (1) Department of Computer Science, University of Wisconsin, Madison, WI 53706, USA. condon@cs.wisc.edu., US;(2) Department of Computer Science, Concordia University, Montreal, Canada H3G 1M8. lata@cs.concordia.ca., CA |
| |
Abstract: | 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. [7] to 1.15n . This improvement is obtained in part by increasing the adaptiveness of previous algorithms. Received May 25, 1995; revised June 1, 1996. |
| |
Keywords: | . Lower bound Selection Mesh Randomized algorithm Adaptiveness. |
本文献已被 SpringerLink 等数据库收录! |
|