Conference paper
Sparse distance preservers and additive spanners
Béla Bollobás, Don Coppersmith, 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 → ∞.
Béla Bollobás, Don Coppersmith, et al.
SODA 1998
Béla Bollobás, Don Coppersmith, et al.
SIAM Journal on Discrete Mathematics
Dimitris Bertsimas, David Gamarnik, et al.
Machine Learning
David Gamarnik, Dmitriy Katz
SODA 2009