Conference paper
Random MAX SAT, random MAX CUT, and their phase transitions
Don Coppersmith, David Gamarnik, et al.
SODA 1998
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 1998
David Gamarnik, Mark S. Squillante
Stochastic Models
Abraham D. Flaxman, David Gamarnik, et al.
Random Structures and Algorithms
David Gamarnik, Tomasz Nowicki, et al.
Random Structures and Algorithms