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.

[2]

K. Cai and G. Han, Coding advantage in communications among peers, in Proc. ISIT, (2016), 2309–2313. doi: 10.1109/ISIT.2016.7541711.

[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.

[4]

K. Cai and G. Han, On the Langberg-Médard $k$-unicast conjecture with k = 3, 4, in Proc. ISIT, (2018).

[5]

K. Cai and G. Han, The Langberg-Médard multiple unicast conjecture: Stable 3-pair networks, in Proc. ISIT, (2020).

[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.

[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.

[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.

[9]

Z. Li and B. Li, Network coding: The case of multiple unicast sessions, in Proc. 42nd Annual Allerton, (2004).

[10]

Z. Li and C. Wu, Space information flow: Multiple unicast, in Proc. ISIT 2012, (2012), 1897–1901. doi: 10.1109/ISIT.2012.6283627.

[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.

[12]

A. Schrijver, Combinatorial Optimization, Springer-Verlag, 2003.

[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.

[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.

[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.

[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.

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.

[2]

K. Cai and G. Han, Coding advantage in communications among peers, in Proc. ISIT, (2016), 2309–2313. doi: 10.1109/ISIT.2016.7541711.

[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.

[4]

K. Cai and G. Han, On the Langberg-Médard $k$-unicast conjecture with k = 3, 4, in Proc. ISIT, (2018).

[5]

K. Cai and G. Han, The Langberg-Médard multiple unicast conjecture: Stable 3-pair networks, in Proc. ISIT, (2020).

[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.

[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.

[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.

[9]

Z. Li and B. Li, Network coding: The case of multiple unicast sessions, in Proc. 42nd Annual Allerton, (2004).

[10]

Z. Li and C. Wu, Space information flow: Multiple unicast, in Proc. ISIT 2012, (2012), 1897–1901. doi: 10.1109/ISIT.2012.6283627.

[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.

[12]

A. Schrijver, Combinatorial Optimization, Springer-Verlag, 2003.

[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.

[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.

[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.

[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.

[1]

Keisuke Minami, Takahiro Matsuda, Tetsuya Takine, Taku Noguchi. Asynchronous multiple source network coding for wireless broadcasting. Numerical Algebra, Control and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 © 2022 American Institute of Mathematical Sciences | Privacy Policy