The random graph threshold for k-orientiability and a fast algorithm for optimal multiple-choice allocation

73 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

PIR with Compressed Queries and Amortized Query Processing (2018, background): “Optimal solutions for this problem can be computed in polynomial time [29], and linear time approximations also exist [24, 34, 41].”
Backyard Cuckoo Hashing: Constant Worst-Case Operations with a Succinct Representation (2009, background): “For further and improved analysis see also [CSW07, DM09, DGM+10, FR07, FP09, FM09, FMM09, LP09].”
Tight Thresholds for Cuckoo Hashing via XORSAT (2009, methodology): “The conjecture is backed by a simple algorithm adapted from Sanders' sel ess algorithm [26,3] that can be found in the full version of this paper [8, preliminary full version].”
Balls into Bins Made Faster (2013, background): “Fernholz and Ramachandran [3] and Cain, Sanders, and Wormald [2] gave linear time algorithms for computing an optimal allocation (asymptotically almost surely).”
The k-orientability thresholds for Gn, p (2007, result): “Concurrent with our paper the same result is reported in [3] using a different method.”