Fast Deterministic Selection

DOI10.4230/LIPICS.SEA.2017.24MaRDI QIDQ4580181zbMATH OpenOpenAlexFDO

Authors A. Alexandrescu

Publication date 13 August 2018

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

zbMATH Keywords

selection problemQuickselectalgorithm engineeringalgorithmic librariesmedian of medians

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Searching and sorting (68P10)

Abstract: The Median of Medians (also known as BFPRT) algorithm, although a landmark theoretical achievement, is seldom used in practice because it and its variants are slower than simple approaches based on sampling. The main contribution of this paper is a fast linear-time deterministic selection algorithm QuickselectAdaptive based on a refined definition of MedianOfMedians. The algorithm's performance brings deterministic selection---along with its desirable properties of reproducible runs, predictable run times, and immunity to pathological inputs---in the range of practicality. We demonstrate results on independent and identically distributed random inputs and on normally-distributed inputs. Measurements show that QuickselectAdaptive is faster than state-of-the-art baselines.

Recommendations

• An optimally efficient selection algorithm
• QUICKSELECT revisited
• Fast deterministic selection on mesh-connected processor arrays
• scientific article; zbMATH DE number 4213428
• scientific article; zbMATH DE number 4082988
• Faster subset selection for matrices and applications
• Parallel Selection with High Probability
• scientific article; zbMATH DE number 1180486
• A parallel selection algorithm

Cited in

(14)

• Trimmed Harrell-Davis quantile estimator based on the highest density interval of the given width
• On O(n) algorithms for projection onto the top-k-sum sublevel set
• Selection Algorithms with Small Groups
• LOL selection in high dimension
• An improved, randomized algorithm for parallel selection with an experimental study
• Approximating the smallest \(k\)-enclosing geodesic disc in a simple polygon
• scientific article; zbMATH DE number 7765400 (Why is no real title available?)
• MedianOfNinthers
• A fast algorithm for quadratic resource allocation problems with nested constraints
• Finding a mediocre player
• scientific article; zbMATH DE number 3909606 (Why is no real title available?)
• A selectable sloppy heap
• Lightweight approximate selection
• On a Reduction for a Class of Resource Allocation Problems

Describes a project that uses

Uses Software

• GitHub

This page was built for publication: Fast Deterministic Selection

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