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. HarveyR. 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. JainV. 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. XuX. ChenJ. LiC. WangY. 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. YangX. YinX. ChenY. 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. HarveyR. 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. JainV. 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. XuX. ChenJ. LiC. WangY. 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. YangX. YinX. ChenY. 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

[Back to Top]