Finding a mediocre player

DOI10.1016/J.DAM.2021.01.006MaRDI QIDQ5925497zbMATH OpenOpenAlexFDO

Authors Adrian Dumitrescu

Publication date 25 March 2021

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2021.01.006

zbMATH Keywords

quantilesrandomized algorithmtournamentsapproximate selectioncomparison algorithmmediocre element\(i\)-th order statisticYao's hypothesis

Mathematics Subject Classification ID

Theory of data (68Pxx) Computer science (68-XX)

Recommendations

• Finding a mediocre player
• scientific article; zbMATH DE number 910857
• Average case selection
• Selecting the Median
• On lower bounds for selecting the median

Cites work

• scientific article; zbMATH DE number 3909739 (Why is no real title available?)
• scientific article; zbMATH DE number 3767009 (Why is no real title available?)
• scientific article; zbMATH DE number 3596259 (Why is no real title available?)
• scientific article; zbMATH DE number 1033192 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• scientific article; zbMATH DE number 3342853 (Why is no real title available?)
• A Counting Approach to Lower Bounds for Selection Problems
• A Unified Lower Bound for Selection and Set Partitioning Problems
• A selectable sloppy heap
• Average case selection
• Expected time bounds for selection
• Fast Deterministic Selection
• Finding the n-th largest element
• Finding the median
• Introduction to algorithms.
• Median selection requires (2+)n comparisons
• New upper bounds for selection
• On lower bounds for selecting the median
• On the Complexity of Partial Order Productions
• Optimal sampling strategies for quicksort
• Optimal sampling strategies in Quicksort and Quickselect
• Probability and Computing
• Producing posets
• Progress in selection
• Selecting the Median
• Selection Algorithms with Small Groups
• Time bounds for selection
• Worst-case efficient sorting with QuickMergesort

Cited in

(1)

• Finding a mediocre player

Describes a project that uses

Uses Software

• MedianOfNinthers
• Find

This page was built for publication: Finding a mediocre player

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