Maintaining discrete probability distributions optimally

DOI10.1007/3-540-56939-1_77zbMath1418.68158OpenAlexW1523494361MaRDI QIDQ4630265

Kurt Mehlhorn, Torben Hagerup, J. Ian Munro

Publication date: 29 March 2019

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-56939-1_77

zbMATH Keywords

generalized distributionabstract data typegarbage collectortable lookupbase segmentnaive algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Abstract data types; algebraic specification (68Q65) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (10)

Dynamic sampling from a discrete probability distribution with a known distribution of rates ⋮ Efficient sampling methods for discrete distributions ⋮ A compact data structure for representing a dynamic multiset ⋮ Parallel Weighted Random Sampling ⋮ Rescorla-Wagner models with sparse dynamic attention ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A nearly linear-time PTAS for explicit fractional packing and covering linear programs ⋮ Practical algorithms for generating a random ordering of the elements of a weighted set ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Worst-case optimal insertion and deletion methods for decomposable searching problems
• Generating Markov-Chain Transitions Quickly: I
• Fast algorithms for generating discrete random variates with changing distributions

This page was built for publication: Maintaining discrete probability distributions optimally