David Gamarnik
Probability Theory and Related Fields
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 → ∞.
David Gamarnik
Probability Theory and Related Fields
David Gamarnik
IEEE Trans. Inf. Theory
David Gamarnik, John Hasenbein
ACM SIGMETRICS Performance Evaluation Review 2003
Richard Arratia, Béla Bollobás, et al.
Combinatorica