Concepedia

The complexity of selection and ranking in X + Y and matrices with sorted columns

Greg N. Frederickson, D. Barton Johnson

Journal of Computer and System Sciences · 1982 · 261 citations · 8 references

DOI

Concepts

References

8

Time bounds for selection

Manuel Blum, Robert W. Floyd, Vaughan Pratt et al. · Journal of Computer and System Sciences · 1973 · 1.2K citations

, , +2

Discrete Optimization Via Marginal Analysis

Bennett L. Fox · Management Science · 1966 · 385 citations

, , +13

An almost optimal algorithm for unbounded searching

Jon Bentley, Andrew Chi-Chih Yao · Information Processing Letters · 1976 · 312 citations · Full text

, , +8

Selecting the <i>K</i>th Element in $X + Y$ and $X_1 + X_2 + \cdots + X_m $

D. Barton Johnson, Tetsuo Mizoguchi · SIAM Journal on Computing · 1978 · 87 citations

, , +10

A Fast Selection Algorithm and the Problem of Optimum Distribution of Effort

Zvi Galil, Nimrod Megiddo · Journal of the ACM · 1979 · 87 citations · Full text

, , +6