Uniform multicommodity flow in the hypercube with random edge capacities
classification
🧮 math.OC
cs.DSmath.CO
keywords
multicommodityflowscapacitiescloseedgehighhypercubenetwork
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.