Selecting the Median

DOI10.1137/S0097539795288611MaRDI QIDQ4268815zbMATH OpenFDO

Authors Uri Zwick, Dorit Dor

Publication date 28 October 1999

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S0097539795288611

zbMATH Keywords

comparison algorithmsconcrete complexitymedian selection

Mathematics Subject Classification ID

Combinatorics of partially ordered sets (06A07) Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05)

Recommendations

• scientific article; zbMATH DE number 910857
• Median selection requires (2+)n comparisons
• On lower bounds for selecting the median

Cited in

(26)

• Comparing medians
• Computing the update of the repeated median regression line in linear time
• An improved algorithm for finding the median distributively
• Architecture independent parallel selection with applications to parallel priority queues
• Pairs of majority-decomposing functions
• On partial sorting in restricted rounds
• A selectable sloppy heap
• On constant factors in comparison-based geometric algorithms and data structures
• On Floyd and Rivest's SELECT algorithm
• Near-optimal online multiselection in internal and external memory
• On the upper bound of the complexity of sorting
• Nearest neighbor representations of Boolean functions
• Median selection requires (2+)n comparisons
• scientific article; zbMATH DE number 1629859 (Why is no real title available?)
• Select with groups of 3 or 4
• Range Medians
• Average case selection
• Optimal execution in Hong Kong given a market-on-close benchmark
• scientific article; zbMATH DE number 910857 (Why is no real title available?)
• Selection Algorithms with Small Groups
• Progress in selection
• On median and quartile sets of ordered random variables
• Finding a mediocre player
• Finding a mediocre player
• scientific article; zbMATH DE number 7765400 (Why is no real title available?)
• Deterministic cache-oblivious funnelselect

This page was built for publication: Selecting the Median

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4268815)