Median Selection Requires $(2+\epsilon)n$ Comparisons
From MaRDI portal
Publication:2719174
DOI10.1137/S0895480199353895zbMath0977.68041MaRDI QIDQ2719174
Publication date: 21 June 2001
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Combinatorics of partially ordered sets (06A07)
Related Items (10)
Progress in selection ⋮ Architecture independent parallel selection with applications to parallel priority queues ⋮ Feasible Iteration of Feasible Learning Functionals ⋮ Range Medians ⋮ Finding a non-minority ball with majority answers ⋮ Comparator networks for binary heap construction ⋮ Finding a mediocre player ⋮ Comparator networks for binary heap construction ⋮ On Floyd and Rivest's SELECT algorithm ⋮ On constant factors in comparison-based geometric algorithms and data structures
This page was built for publication: Median Selection Requires $(2+\epsilon)n$ Comparisons
