The complexity of selection and ranking in X + Y and matrices with sorted columns
Authors:
- Greg N. FredericksonGFGreg N. Frederickson
- Donald B. JohnsonDJDonald B. Johnson
- 1 April 1982
- journal article
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 24 (2) , 197-208
Abstract
No abstract availableKeywords
This publication has 7 references indexed in Scilit:
- A Fast Selection Algorithm and the Problem of Optimum Distribution of EffortJournal of the ACM, 1979
- Lower Bounds for Selection in X + Y and Other MultisetsJournal of the ACM, 1978
- Selecting the Kth Element in $X + Y$ and $X_1 + X_2 + \cdots + X_m $SIAM Journal on Computing, 1978
- An almost optimal algorithm for unbounded searchingInformation Processing Letters, 1976
- Time bounds for selectionJournal of Computer and System Sciences, 1973
- Proving simultaneous positivity of linear formsJournal of Computer and System Sciences, 1972
- Discrete Optimization Via Marginal AnalysisManagement Science, 1966