Choice-memory tradeoff in allocations

DOI10.1214/09-AAP656zbMath1205.60023arXiv0901.4056MaRDI QIDQ990388

Noga Alon, Ori Gurel-Gurevich, Eyal Lubetzky

Publication date: 1 September 2010

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

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

zbMATH Keywords

balls and bins paradigmspace/performance tradeoffs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Sums of independent random variables; random walks (60G50) Combinatorial probability (60C05)

Related Items

On Approximating the Stationary Distribution of Time-reversible Markov Chains, Long-term balanced allocation via thinning, On approximating the stationary distribution of time-reversible Markov chains

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On tail probabilities for martingales
• Time-space tradeoffs for branching programs
• Determinism versus nondeterminism for linear time RAMs with memory restrictions
• A general Sequential Time-Space Tradeoff for Finding Unique Elements
• Time-space lower bounds for satisfiability
• Time-space trade-off lower bounds for randomized computation of decision problems
• Dimension reduction for hyperbolic space
• The Complexity of Parallel Sorting
• Expected Length of the Longest Probe Sequence in Hash Code Searching
• A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
• Percolation
• Balanced Allocations
• Probability and Computing
• A Best Possible Kolmogoroff-Type Inequality for Martingales and a Characteristic Property