# American Institute of Mathematical Sciences

doi: 10.3934/amc.2021001

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

 Department of Mathematics, University of Hong Kong, Hong Kong, no, China

Received  February 2020 Revised  November 2020 Published  March 2021

Fund Project: This research is partly supported by a grant from the Research Grants Council of the Hong Kong Special Administrative Region, China (Project No. 17301017) and a grant by the National Natural Science Foundation of China (Project No. 61871343)

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

Citation: Kai Cai, Guangyue Han. An optimization approach to the Langberg-Médard multiple unicast conjecture. Advances in Mathematics of Communications, doi: 10.3934/amc.2021001
##### References:
 [1] K. Cai and G. Han, On network coding advantage for multiple unicast networks, in Proc. ISIT, (2015), 366–370. doi: 10.1109/ISIT.2015.7282478.  Google Scholar [2] K. Cai and G. Han, Coding advantage in communications among peers, in Proc. ISIT, (2016), 2309–2313. doi: 10.1109/ISIT.2016.7541711.  Google Scholar [3] K. Cai and G. Han, On the Langberg-Médard multiple unicast conjecture, Journal of Combinatorial Optimization, 34 (2017), 1114-1132.  doi: 10.1007/s10878-017-0132-2.  Google Scholar [4] K. Cai and G. Han, On the Langberg-Médard $k$-unicast conjecture with k = 3, 4, in Proc. ISIT, (2018). Google Scholar [5] K. Cai and G. Han, The Langberg-Médard multiple unicast conjecture: Stable 3-pair networks, in Proc. ISIT, (2020). Google Scholar [6] N. Harvey, R. Kleinberg and A. Lehman, On the capacity of information networks, IEEE Trans. Inf. Theory, 52 (2006), 2345-2364.  doi: 10.1109/TIT.2006.874531.  Google Scholar [7] K. Jain, V. V. Vazirani and G. Yuval, On the capacity of multiple unicast sessions in undirected graphs, IEEE/ACM Trans. Networking, 14 (2006), 2805-2809.  doi: 10.1109/TIT.2006.874543.  Google Scholar [8] M. Langberg and M. M$\acute{e}$dard, On the multiple unicast network coding conjecture, in Proc. 47th Annual Allerton, (2009), 222–227. doi: 10.1109/ALLERTON.2009.5394800.  Google Scholar [9] Z. Li and B. Li, Network coding: The case of multiple unicast sessions, in Proc. 42nd Annual Allerton, (2004). Google Scholar [10] Z. Li and C. Wu, Space information flow: Multiple unicast, in Proc. ISIT 2012, (2012), 1897–1901. doi: 10.1109/ISIT.2012.6283627.  Google Scholar [11] J. Li, X. Chen, X. Sun, Z. Li, and Y. Yang, Quantum network coding for multi-unicast problem based on 2D and 3D cluster states, Science China-Information Sciences, 59 (2016), 042301. doi: 10.1007/s11432-016-5539-3.  Google Scholar [12] A. Schrijver, Combinatorial Optimization, Springer-Verlag, 2003. Google Scholar [13] T. Xiahou, C. Wu, J. Huang and Z. Li, A geometric framework for investigating the multiple unicast network coding conjecture, in Proc. NetCod, (2012), 37–42. doi: 10.1109/NETCOD.2012.6261881.  Google Scholar [14] G. Xu, X. Chen, J. Li, C. Wang, Y. Yang and Z. Li, Network coding for quantum cooperative multicast, Quantum Information Processing, 14 (2015), 4297-4322.  doi: 10.1007/s11128-015-1098-6.  Google Scholar [15] Y. Yang, X. Yin, X. Chen, Y. Yang and Z. Li, A note on the multiple-unicast network coding conjecture, IEEE Communications Letters, 18 (2014), 869-872.  doi: 10.1109/LCOMM.2014.040214.140280.  Google Scholar [16] R. Yeung, S.-Y. Li, and N. Cai, Network Coding Theory (Foundations and Trends in Communications and Information Theory), Now Publishers Inc., Hanover, MA, USA, 2006. Google Scholar

show all references

##### References:
 [1] K. Cai and G. Han, On network coding advantage for multiple unicast networks, in Proc. ISIT, (2015), 366–370. doi: 10.1109/ISIT.2015.7282478.  Google Scholar [2] K. Cai and G. Han, Coding advantage in communications among peers, in Proc. ISIT, (2016), 2309–2313. doi: 10.1109/ISIT.2016.7541711.  Google Scholar [3] K. Cai and G. Han, On the Langberg-Médard multiple unicast conjecture, Journal of Combinatorial Optimization, 34 (2017), 1114-1132.  doi: 10.1007/s10878-017-0132-2.  Google Scholar [4] K. Cai and G. Han, On the Langberg-Médard $k$-unicast conjecture with k = 3, 4, in Proc. ISIT, (2018). Google Scholar [5] K. Cai and G. Han, The Langberg-Médard multiple unicast conjecture: Stable 3-pair networks, in Proc. ISIT, (2020). Google Scholar [6] N. Harvey, R. Kleinberg and A. Lehman, On the capacity of information networks, IEEE Trans. Inf. Theory, 52 (2006), 2345-2364.  doi: 10.1109/TIT.2006.874531.  Google Scholar [7] K. Jain, V. V. Vazirani and G. Yuval, On the capacity of multiple unicast sessions in undirected graphs, IEEE/ACM Trans. Networking, 14 (2006), 2805-2809.  doi: 10.1109/TIT.2006.874543.  Google Scholar [8] M. Langberg and M. M$\acute{e}$dard, On the multiple unicast network coding conjecture, in Proc. 47th Annual Allerton, (2009), 222–227. doi: 10.1109/ALLERTON.2009.5394800.  Google Scholar [9] Z. Li and B. Li, Network coding: The case of multiple unicast sessions, in Proc. 42nd Annual Allerton, (2004). Google Scholar [10] Z. Li and C. Wu, Space information flow: Multiple unicast, in Proc. ISIT 2012, (2012), 1897–1901. doi: 10.1109/ISIT.2012.6283627.  Google Scholar [11] J. Li, X. Chen, X. Sun, Z. Li, and Y. Yang, Quantum network coding for multi-unicast problem based on 2D and 3D cluster states, Science China-Information Sciences, 59 (2016), 042301. doi: 10.1007/s11432-016-5539-3.  Google Scholar [12] A. Schrijver, Combinatorial Optimization, Springer-Verlag, 2003. Google Scholar [13] T. Xiahou, C. Wu, J. Huang and Z. Li, A geometric framework for investigating the multiple unicast network coding conjecture, in Proc. NetCod, (2012), 37–42. doi: 10.1109/NETCOD.2012.6261881.  Google Scholar [14] G. Xu, X. Chen, J. Li, C. Wang, Y. Yang and Z. Li, Network coding for quantum cooperative multicast, Quantum Information Processing, 14 (2015), 4297-4322.  doi: 10.1007/s11128-015-1098-6.  Google Scholar [15] Y. Yang, X. Yin, X. Chen, Y. Yang and Z. Li, A note on the multiple-unicast network coding conjecture, IEEE Communications Letters, 18 (2014), 869-872.  doi: 10.1109/LCOMM.2014.040214.140280.  Google Scholar [16] R. Yeung, S.-Y. Li, and N. Cai, Network Coding Theory (Foundations and Trends in Communications and Information Theory), Now Publishers Inc., Hanover, MA, USA, 2006. Google Scholar
 [1] Arseny Egorov. Morse coding for a Fuchsian group of finite covolume. Journal of Modern Dynamics, 2009, 3 (4) : 637-646. doi: 10.3934/jmd.2009.3.637 [2] Roberto Civino, Riccardo Longo. Formal security proof for a scheme on a topological network. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021009 [3] Yuncherl Choi, Taeyoung Ha, Jongmin Han, Sewoong Kim, Doo Seok Lee. Turing instability and dynamic phase transition for the Brusselator model with multiple critical eigenvalues. Discrete & Continuous Dynamical Systems, 2021  doi: 10.3934/dcds.2021035 [4] Xiaochen Mao, Weijie Ding, Xiangyu Zhou, Song Wang, Xingyong Li. Complexity in time-delay networks of multiple interacting neural groups. Electronic Research Archive, , () : -. doi: 10.3934/era.2021022 [5] Claudianor O. Alves, Giovany M. Figueiredo, Riccardo Molle. Multiple positive bound state solutions for a critical Choquard equation. Discrete & Continuous Dynamical Systems, 2021  doi: 10.3934/dcds.2021061 [6] Rui Hu, Yuan Yuan. Stability, bifurcation analysis in a neural network model with delay and diffusion. Conference Publications, 2009, 2009 (Special) : 367-376. doi: 10.3934/proc.2009.2009.367 [7] Jingni Guo, Junxiang Xu, Zhenggang He, Wei Liao. Research on cascading failure modes and attack strategies of multimodal transport network. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2020159 [8] Andrey Kovtanyuk, Alexander Chebotarev, Nikolai Botkin, Varvara Turova, Irina Sidorenko, Renée Lampe. Modeling the pressure distribution in a spatially averaged cerebral capillary network. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021016 [9] Cheng-Kai Hu, Fung-Bao Liu, Hong-Ming Chen, Cheng-Feng Hu. Network data envelopment analysis with fuzzy non-discretionary factors. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1795-1807. doi: 10.3934/jimo.2020046 [10] Guanwei Chen, Martin Schechter. Multiple solutions for Schrödinger lattice systems with asymptotically linear terms and perturbed terms. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021124 [11] Reza Lotfi, Yahia Zare Mehrjerdi, Mir Saman Pishvaee, Ahmad Sadeghieh, Gerhard-Wilhelm Weber. A robust optimization model for sustainable and resilient closed-loop supply chain network design considering conditional value at risk. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 221-253. doi: 10.3934/naco.2020023 [12] Saeed Assani, Muhammad Salman Mansoor, Faisal Asghar, Yongjun Li, Feng Yang. Efficiency, RTS, and marginal returns from salary on the performance of the NBA players: A parallel DEA network with shared inputs. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021053 [13] Haodong Chen, Hongchun Sun, Yiju Wang. A complementarity model and algorithm for direct multi-commodity flow supply chain network equilibrium problem. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2217-2242. doi: 10.3934/jimo.2020066 [14] Ru Li, Guolin Yu. Strict efficiency of a multi-product supply-demand network equilibrium model. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2203-2215. doi: 10.3934/jimo.2020065

2019 Impact Factor: 0.734

Article outline