David Gamarnik, Dmitriy Katz
Journal of Computer and System Sciences
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, Dmitriy Katz
Journal of Computer and System Sciences
David Gamarnik
Probability Theory and Related Fields
Abraham Flaxman, David Gamarnik, et al.
Random Structures and Algorithms
David Gamarnik, Dmitriy Katz-Rogozhnikov
Queueing Systems