Select with Groups of 3 or 4

DOI10.1007/978-3-319-21840-3_16zbMath1444.68127OpenAlexW1836666292MaRDI QIDQ3449816

Adrian Dumitrescu, Ke Chen

Publication date: 30 October 2015

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-21840-3_16

zbMATH Keywords

median selectioncomparison algorithm\(i\)th order statistic

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Combinatorics in computer science (68R05) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Related Items (1)

A selectable sloppy heap

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• 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
• A Counting Approach to Lower Bounds for Selection Problems
• Selecting the Median
• Progress in selection
• Probability and Computing

This page was built for publication: Select with Groups of 3 or 4