Generalized selection and ranking (Preliminary Version)
- 1 January 1980
- proceedings article
- Published by Association for Computing Machinery (ACM)
- p. 420-428
- https://doi.org/10.1145/800141.804690
Abstract
Selection in a set requires time linear in the size of the set when there are no a priori constraints on the total orders possible for the set. Constraints often come for free, however, with sets which arise in applications. Linear time selection [Bl] can be suboptimal for such problems. We therefore generalize the well known selection problem to admit constraints on the input sets, with a view toward settling the complexity issues which arise. The generalization also applies to the other quantile problems of ranking a given element in the input set and verification of the claim that a given element has a specified rank.Keywords
This publication has 0 references indexed in Scilit: