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]

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]

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

[3]

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

[4]

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

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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

[16]

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

[17]

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

[18]

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

[19]

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

[20]

K. H. Kim and F. W. Roush. The Williams conjecture is false for irreducible subshifts. Electronic Research Announcements, 1997, 3: 105-109.

2019 Impact Factor: 0.734

Metrics

  • PDF downloads (28)
  • HTML views (105)
  • Cited by (0)

Other articles
by authors

[Back to Top]