An optimization approach to the Langberg-Médard multiple unicast conjecture

The Langberg-Medard multiple unicast conjecture claims that for any strongly reachable \begin{document}$ k $\end{document} -pair network, there exists a multi-flow with rate \begin{document}$ (1,1,\dots,1) $\end{document} . In this paper, we examine an optimization problem \begin{document}$ \mathcal P_{\mathcal S_k} $\end{document} such that its optimal value \begin{document}$ \mathcal O_{\mathcal S_k} $\end{document} naturally gives a lower bound on the multi-flow rate for the strongly reachable \begin{document}$ k $\end{document} -pair network. We first prove \begin{document}$ \lim_{k\rightarrow \infty}\mathcal O_{\mathcal S_k} = \frac{9}{8} $\end{document} and then show that the multi-flow \begin{document}$ \mathcal C^*_k $\end{document} constructed in our previous work is asymptotically optimal for \begin{document}$ \mathcal P_{\mathcal S_k} $\end{document} and optimal if and only if \begin{document}$ k = 1, 2, 6, 10 $\end{document} .