Quickselect and the Dickman Function
From MaRDI portal
Publication:3146984
DOI10.1017/S0963548302005138zbMath1008.68044OpenAlexW1992422944MaRDI QIDQ3146984
Tsung-Hsi Tsai, Hsien-Kuei Hwang
Publication date: 21 October 2002
Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1017/s0963548302005138
Related Items (30)
On the contraction method with degenerate limit equation. ⋮ Simulating the Dickman distribution ⋮ On quickselect, partial sorting and multiple Quickselect ⋮ Fast perfect simulation of Vervaat perpetuities ⋮ Appendix to ``Approximating perpetuities ⋮ Approximating perpetuities ⋮ Density functions for \texttt{QuickQuant} and \texttt{QuickVal} ⋮ Classical and almost sure local limit theorems ⋮ Convergence to scale-invariant Poisson processes and applications in Dickman approximation ⋮ Analysis of the expected number of bit comparisons required by quickselect ⋮ The analysis of range quickselect and related problems ⋮ A general limit theorem for recursive algorithms and combinatorial structures ⋮ On the properties of a Takács distribution ⋮ On strong and almost sure local limit theorems for a probabilistic model of the Dickman distribution ⋮ On edge-weighted recursive trees and inversions in random permutations ⋮ On the strange domain of attraction to generalized Dickman distributions for sums of independent random variables ⋮ Non-asymptotic distributional bounds for the Dickman approximation of the running time of the Quickselect algorithm ⋮ Analysis of swaps in radix selection ⋮ Distributional analysis of swaps in quick select ⋮ Random minimal directed spanning trees and Dickman-type distributions ⋮ The Dickman subordinator, renewal theorems, and disordered systems ⋮ Asymptotic results for weighted means of random variables which converge to a Dickman distribution, and some number theoretical applications ⋮ Convergence to type I distribution of the extremes of sequences defined by random difference equation ⋮ Almost sure local limit theorem for the Dickman distribution ⋮ On weighted depths in random binary search trees ⋮ Mixed distributions in Sattolo's algorithm for cyclic permutations via randomization and derandomization ⋮ Local limit theorems in some random models from number theory ⋮ Distributional Convergence for the Number of Symbol Comparisons Used by Quickselect ⋮ Dickman approximation in simulation, summations and perpetuities ⋮ Analysis of quickselect under Yaroslavskiy's dual-pivoting algorithm
This page was built for publication: Quickselect and the Dickman Function
