On Floyd and Rivest's SELECT algorithm
From MaRDI portal
Publication:2576874
DOI10.1016/j.tcs.2005.06.032zbMath1080.68040OpenAlexW1984371651WikidataQ56337164 ScholiaQ56337164MaRDI QIDQ2576874
Publication date: 29 December 2005
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://rcin.org.pl/dlibra/docmetadata?showContent=true&id=139623
Related Items
Fast projection onto the simplex and the \(l_1\) ball, Algorithms for the continuous nonlinear resource allocation problem -- new implementations and numerical studies, On a Reduction for a Class of Resource Allocation Problems, A fast algorithm for quadratic resource allocation problems with nested constraints, A Newton's method for the continuous quadratic knapsack problem, Variable fixing algorithms for the continuous quadratic Knapsack problem, BlockQuicksort, Breakpoint searching algorithms for the continuous quadratic knapsack problem, On linear-time algorithms for the continuous quadratic Knapsack problem, Homogeneous string segmentation using trees and weighted independent sets
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Randomized selection in \(n+C+o(n)\) comparisons
- Finding the median
- The tail of the hypergeometric distribution
- Time bounds for selection
- On the computational power of pushdown automata
- On Lower Bounds for Selecting the Median
- Median Selection Requires $(2+\epsilon)n$ Comparisons
- Optimal Sampling Strategies in Quicksort and Quickselect
- Analysis of Hoare's FIND algorithm with Median-of-three partition
- Probabilistic Parallel Algorithms for Sorting and Selection
- Average case selection
- Expected time bounds for selection
- Quicksort with Equal Keys
- On the median-of-k version of Hoare's selection algorithm
- Selecting the Median
- Introspective sorting and selection revisited
- Probability Inequalities for Sums of Bounded Random Variables
