Uniform multicommodity flows in the hypercube with random edge‐capacities. Issue 3 (7th November 2016) - McDiarmid, Colin; Scott, Alex; Withers, Paul
ABSTRACT: We give two results for multicommodity flows in the d ‐dimensional hypercube Q d with independent random edge‐capacities distributed like a random variable C where ℙ [ C > 0 ] > 1 / 2 . Firstly, with high probability as d → ∞, the network can support simultaneous multicommodity flows of volume close to E [ C ] between all antipodal vertex pairs. Secondly, with high probability, the network can support simultaneous multicommodity flows of volume close to 2 1 − d E [ C ] between all vertex pairs. Both results are best possible. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 437–463, 2017