Conference paper
The diameter of a long range percolation graph
Don Coppersmith, David Gamarnik, et al.
SODA 2002
Consider a complete graph on n vertices with edge weights chosen randomly and independently from an exponential distribution with parameter 1. Fix k vertices and consider the minimum weight Steiner tree which contains these vertices. We prove that with high probability the weight of this tree is (1 + o(1))(k - 1)(logn - log k)/n when k = o(n) and n → ∞.
Don Coppersmith, David Gamarnik, et al.
SODA 2002
David Gamarnik
SODA 2004
David Gamarnik, John Hasenbein
ACM SIGMETRICS Performance Evaluation Review 2003
David Gamarnik, Tomasz Nowicki, et al.
Ergodic Theory and Dynamical Systems