Selection Algorithms with Small Groups

DOI10.1142/S0129054120500136zbMath1458.68292arXiv1409.3600OpenAlexW3023681931MaRDI QIDQ4983545

Adrian Dumitrescu, Ke Chen

Publication date: 20 April 2021

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1409.3600

zbMATH Keywords

median selectioncomparison algorithm\(i\)th-order statistic

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorics in computer science (68R05)

Related Items (2)

Unnamed Item ⋮ Finding a mediocre player

Uses Software

• Find
• MedianOfNinthers

Cites Work

• Optimal parallel selection has complexity O(log log N)
• Finding the median
• Time bounds for selection
• Finding the \(\alpha n\)-th largest element
• On Lower Bounds for Selecting the Median
• Closing a Long-Standing Complexity Gap for Selection: V 3(42) = 50
• Partitioning with two lines in the plane
• The Ultimate Planar Convex Hull Algorithm?
• A New Lower Bound for the Set-Partitioning Problem
• Average case selection
• A Unified Lower Bound for Selection and Set Partitioning Problems
• On the Average-Case Complexity of Selecting the kth Best
• Expected time bounds for selection
• Bounds for Selection
• New upper bounds for selection
• A Counting Approach to Lower Bounds for Selection Problems
• Selecting the Median
• Fast Deterministic Selection
• Progress in selection
• Probability and Computing
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Selection Algorithms with Small Groups