Generalized Selection and Ranking (Preliminary Version)

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 [B l ] 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.

Authors

• Greg N. Frederickson
• Donald B. Johnson 0001

Keywords

No keywords are indexed for this paper.