Paper Info
Title
Exact and efficient generation of geometric random variates and random graphs
Abstract
The standard algorithm for fast generation of Erdős-Rényi random graphs only works in the Real RAM model. The critical point is the generation of geometric random variates Geo(p), for which there is no algorithm that is both exact and efficient in any bounded precision machine model. For a RAM model with word size w=Ω(loglog(1/p)), we show that this is possible and present an exact algorithm for sampling Geo(p) in optimal expected time $\mathcal{O}(1 + \log(1/p) / w)$. We also give an exact algorithm for sampling min{n, Geo(p)} in optimal expected time $\mathcal{O}(1 + \log(\operatorname{min}\{1/p,n\})/w)$. This yields a new exact algorithm for sampling Erdős-Rényi and Chung-Lu random graphs of n vertices and m (expected) edges in optimal expected runtime $\mathcal{O}(n + m)$ on a RAM with word size w=Θ(logn).
Year
DOI
Venue
2013
10.1007/978-3-642-39206-1_23
ICALP
Keywords
Field
DocType
geometric random variate,word size w,bounded precision machine model,optimal expected runtime,efficient generation,standard algorithm,real ram model,chung-lu random graph,new exact algorithm,exact algorithm,ram model,optimal expected time
Real RAM,Discrete mathematics,Combinatorics,Random graph,Vertex (geometry),Exact algorithm,Critical point (thermodynamics),Sampling (statistics),Word (computer architecture),Mathematics,Bounded function
Conference
Volume
ISSN
Citations 
7965
0302-9743
4
PageRank 
References 
Authors
0.43
11
2
Name
Order
Citations
PageRank
Karl Bringmann142730.13
Tobias Friedrich245723.56