A Transposition Rule Analysis Based on a Particle Process

DOI10.1239/jap/1110381383zbMath1104.68031arXivmath/0404021OpenAlexW2044765725MaRDI QIDQ5312853

Petar Momčilović, David Gamarnik

Publication date: 25 August 2005

Published in: Journal of Applied Probability (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Searching and sorting (68P10) Data structures (68P05) Limit theorems in probability theory (60F99)

Related Items (1)

Comparison of subdominant eigenvalues of some linear search schemes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Limits and rates of convergence for the distribution of search cost under the move-to-front rule
• Birthday paradox, coupon collectors, caching algorithms and self- organizing search
• Asymptotic approximation of the move-to-front search cost distribution and least-recently used caching fault probabilities
• An exact formula for the move-to-front rule for self-organizing lists
• Self-organizing files with dependent accesses
• Optimal list order under partial memory constraints
• Two Spectra of Self-Organizing Sequential Search Algorithms
• A counterexample to a conjecture on optimal list ordering
• On self-organizing sequential search heuristics
• On the distribution of the search cost for the move-to-front rule with random weights

This page was built for publication: A Transposition Rule Analysis Based on a Particle Process