American Institute of Mathematical Sciences

Advanced
doi: 10.3934/amc.2021001
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

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

Kai Cai and  Guangyue Han

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

Received  February 2020 Revised  November 2020 Early access 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 $.

Keywords: Network coding, multiple unicast conjecture.
Mathematics Subject Classification: Primary: 94B99.
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]

Keisuke Minami, Takahiro Matsuda, Tetsuya Takine, Taku Noguchi. Asynchronous multiple source network coding for wireless broadcasting. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 577-592. doi: 10.3934/naco.2011.1.577
[2]

Ghislain Fourier, Gabriele Nebe. Degenerate flag varieties in network coding. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021027
[3]

Stefan Martignoli, Ruedi Stoop. Phase-locking and Arnold coding in prototypical network topologies. Discrete & Continuous Dynamical Systems - B, 2008, 9 (1) : 145-162. doi: 10.3934/dcdsb.2008.9.145
[4]

Giuseppe Bianchi, Lorenzo Bracciale, Keren Censor-Hillel, Andrea Lincoln, Muriel Médard. The one-out-of-k retrieval problem and linear network coding. Advances in Mathematics of Communications, 2016, 10 (1) : 95-112. doi: 10.3934/amc.2016.10.95
[5]

Lisa Hollman, P. J. McKenna. A conjecture on multiple solutions of a nonlinear elliptic boundary value problem: some numerical evidence. Communications on Pure & Applied Analysis, 2011, 10 (2) : 785-802. doi: 10.3934/cpaa.2011.10.785
[6]

F. Ali Mehmeti, R. Haller-Dintelmann, V. Régnier. Dispersive waves with multiple tunnel effect on a star-shaped network. Discrete & Continuous Dynamical Systems - S, 2013, 6 (3) : 783-791. doi: 10.3934/dcdss.2013.6.783
[7]

Michelle L.F. Cheong, Rohit Bhatnagar, Stephen C. Graves. Logistics network design with supplier consolidation hubs and multiple shipment options. Journal of Industrial & Management Optimization, 2007, 3 (1) : 51-69. doi: 10.3934/jimo.2007.3.51
[8]

Hong Il Cho, Myungwoo Lee, Ganguk Hwang. A cross-layer relay selection scheme of a wireless network with multiple relays under Rayleigh fading. Journal of Industrial & Management Optimization, 2014, 10 (1) : 1-19. doi: 10.3934/jimo.2014.10.1
[9]

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
[10]

Min Ye, Alexander Barg. Polar codes for distributed hierarchical source coding. Advances in Mathematics of Communications, 2015, 9 (1) : 87-103. doi: 10.3934/amc.2015.9.87
[11]

Miguel Mendes. A note on the coding of orbits in certain discontinuous maps. Discrete & Continuous Dynamical Systems, 2010, 27 (1) : 369-382. doi: 10.3934/dcds.2010.27.369
[12]

Alex Eskin, Gregory Margulis and Shahar Mozes. On a quantitative version of the Oppenheim conjecture. Electronic Research Announcements, 1995, 1: 124-130.

[13]

Uri Shapira. On a generalization of Littlewood's conjecture. Journal of Modern Dynamics, 2009, 3 (3) : 457-477. doi: 10.3934/jmd.2009.3.457
[14]

Vitali Kapovitch, Anton Petrunin, Wilderich Tuschmann. On the torsion in the center conjecture. Electronic Research Announcements, 2018, 25: 27-35. doi: 10.3934/era.2018.25.004
[15]

Michael Hutchings, Frank Morgan, Manuel Ritore and Antonio Ros. Proof of the double bubble conjecture. Electronic Research Announcements, 2000, 6: 45-49.

[16]

G. A. Swarup. On the cut point conjecture. Electronic Research Announcements, 1996, 2: 98-100.

[17]

Janos Kollar. The Nash conjecture for threefolds. Electronic Research Announcements, 1998, 4: 63-73.

[18]

Roman Shvydkoy. Lectures on the Onsager conjecture. Discrete & Continuous Dynamical Systems - S, 2010, 3 (3) : 473-496. doi: 10.3934/dcdss.2010.3.473
[19]

Joel Hass, Michael Hutchings and Roger Schlafly. The double bubble conjecture. Electronic Research Announcements, 1995, 1: 98-102.

[20]

Peigen Cao, Fang Li, Siyang Liu, Jie Pan. A conjecture on cluster automorphisms of cluster algebras. Electronic Research Archive, 2019, 27: 1-6. doi: 10.3934/era.2019006

2020 Impact Factor: 0.935

Tools

Article outline

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences