Optimal Multicommodity Flow Through the Complete Graph with Random Edge Capacities
Mustafa Khandwawala, Rajesh Sundaresan · Journal of Applied Probability · 2010
We consider a multicommodity flow problem on a complete graph whose edges have random, independent, and identically distributed capacities. We show that, as the number of nodes tends to infinity, the maximum utility, given by the average of a concave function of each commodity flow, has an almost-sure limit. Furthermore, the asymptotically optimal flow uses only direct and two-hop paths, and can be obtained in a distributed manner.