pith. sign in

arxiv: 1406.4433 · v3 · pith:AMB24AW4new · submitted 2014-06-17 · 🧮 math.OC · cs.DS· math.CO

Uniform multicommodity flow in the hypercube with random edge capacities

classification 🧮 math.OC cs.DSmath.CO
keywords multicommodityflowscapacitiescloseedgehighhypercubenetwork
0
0 comments X
read the original abstract

We give two results for multicommodity flows in the $d$-dimensional hypercube ${Q}^d$ with independent random edge capacities distributed like $C$ where $\Pr[C>0]>1/2$. Firstly, with high probability as $d \rightarrow \infty$, 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.