Selection Algorithms with Small Groups

DOI10.1142/S0129054120500136zbMATH Open1458.68292OpenAlexW3023681931MaRDI QIDQ4983545FDOQ4983545

Authors Ke Chen, Adrian Dumitrescu 

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

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

Abstract: We revisit the selection problem, namely that of computing the $i$th order statistic of $n$ given elements, in particular the classic deterministic algorithm by grouping and partition due to Blum, Floyd, Pratt, Rivest, and Tarjan (1973). Whereas the original algorithm uses groups of odd size at least $5$ and runs in linear time, it has been perpetuated in the literature that using smaller group sizes will force the worst-case running time to become superlinear, namely $Omega(nlogn)$. We first point out that the usual arguments found in the literature justifying the superlinear worst-case running time fall short of proving this claim. We further prove that it is possible to use group size smaller than $5$ while maintaining the worst case linear running time. To this end we introduce three simple variants of the classic algorithm, the repeated step algorithm, the shifting target algorithm, and the hyperpair algorithm, all running in linear time.

Recommendations

• An algorithm for a selection procedure
• An optimally efficient selection algorithm
• Optimal subgroup selection
• New algorithms for selection
• Selection problem with applications
• A random-size subset approach to the selection problem
• Choice via grouping procedures
• Optimal partitioning of groups in selecting the best choice

Cites Work

• 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 3633709 (Why is no real title available?)
• scientific article; zbMATH DE number 1033192 (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 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
• Fast Deterministic Selection
• Finding the \(\alpha n\)-th largest element
• Finding the median
• Introduction to algorithms.
• New upper bounds for selection
• 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
• The Ultimate Planar Convex Hull Algorithm?
• Time bounds for selection

Cited In (4)

• Title not available (Why is no real title available?)
• Probabilistic analysis of a grouping algorithm
• Finding a mediocre player
• Select with groups of 3 or 4

Uses Software

• Find
• MedianOfNinthers

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

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