-
Previous Article
Infinite families of 2-designs from a class of non-binary Kasami cyclic codes
- AMC Home
- This Issue
-
Next Article
New discrete logarithm computation for the medium prime case using the function field sieve
An optimization approach to the Langberg-Médard multiple unicast conjecture
Department of Mathematics, University of Hong Kong, Hong Kong, no, China |
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 $.
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). 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. |
[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). 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. |
[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. 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. |
[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. 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. |
[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). 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. |
[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). 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. |
[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. 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. |
[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. 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
Tools
Article outline
[Back to Top]