Select with groups of 3 or 4

DOI10.1007/978-3-319-21840-3_16MaRDI QIDQ3449816zbMATH OpenOpenAlexFDO

Authors Ke Chen, Adrian Dumitrescu

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

\(i\)th order statisticcomparison algorithmmedian selection

Mathematics Subject Classification ID

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

Recommendations

• Selection Algorithms with Small Groups
• On Floyd and Rivest's SELECT algorithm
• Automata, Languages and Programming
• Average case selection
• A probabilistic analysis of the Floyd–Rivest expected time selection algorithm

Cites work

• A Counting Approach to Lower Bounds for Selection Problems
• A New Lower Bound for the Set-Partitioning Problem
• A Unified Lower Bound for Selection and Set Partitioning Problems
• Average case selection
• Bounds for Selection
• Closing a long-standing complexity gap for selection: \(V _{3}(42) = 50\)
• Expected time bounds for selection
• Finding the n-th largest element
• Finding the median
• scientific article; zbMATH DE number 1629859 (Why is no real title available?)
• scientific article; zbMATH DE number 3767009 (Why is no real title available?)
• scientific article; zbMATH DE number 1052006 (Why is no real title available?)
• scientific article; zbMATH DE number 3342853 (Why is no real title available?)
• Introduction to algorithms.
• On lower bounds for selecting the median
• On the Average-Case Complexity of Selecting the kth Best
• Optimal parallel selection has complexity O(log log N)
• Partitioning with two lines in the plane
• Probability and Computing
• Progress in selection
• Selecting the Median
• Time bounds for selection

Cited in

(3)

• A selectable sloppy heap
• Closing a long-standing complexity gap for selection: \(V _{3}(42) = 50\)
• Probabilistic analysis of a grouping algorithm

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

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