Dimitris Bertsimas, David Gamarnik, et al.
Machine Learning
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 → ∞.
Dimitris Bertsimas, David Gamarnik, et al.
Machine Learning
Don Coppersmith, David Gamarnik, et al.
SODA 2002
David Gamarnik, Dmitriy Katz
Journal of Statistical Physics
Dimitris Bertsimas, David Gamarnik
Journal of Algorithms