Linear Programming Problems in Network Coding and Closure Operators via Partitions

Authors

DOI:

https://doi.org/10.17268/sel.mat.2019.02.12

Keywords:

Directed graph, network code, closure operator, representable matroid, linear rank inequality

Abstract

A network is an acyclic directed graph in which there are sources that have some messages and want to transmit to receivers through the combination of messages in intermediate nodes. The goal is to find a collection of functions that allow to combine messages in order to satisfy the demand of the receivers. In this paper, we study the fractional solvability problem of a network using an extension of the solvability problem in closure operators given by Gadouleau in 2013. We define linear programming problems via the desired extension in order to study capacities; using some information inequalities and characteristic-dependent linear rank inequalities, we obtain upper bounds on linear capacity of some networks and closure operators over some fields.

References

Ahlswede R., Cai N., Li S.-Y. R. & Yeung R. W., Network information flow, IEEE Trans. Inform. Theory, 2000; 46:1204-1216 .

Blasiak A., Kleinberg R. & Lubetzky E., Lexicographic products and the power of non-Linear Network Coding, IEEE Symposium on Foundations of Computer Science, 2011; 609-618.

Brickell E. F. & Davenport D. M., On the classification of Ideal Secret Sharing, J. of Cryptology, 1991; 4:123-134.

Burris S. & Sankappanavar H. P., A course in Universal Algebra, Springer-Verlag 1981.

Dougherty R., Freiling C. & Zeger K., Insufficiency of linear coding in network information flow, IEEE Transactions on Information Theory, 2005; 51(8):2745-2759.

Dougherty R., Freiling C. & Zeger K., Networks, Matroids, and non-Shannon Information Inequalities, IEEE Trans. on Information Theory, 2007; 3(6):1949-1969.

Dougherty R., Freiling C. & Zeger K., Linear Rank Inequalities on five or more variables, arXiv:0910.0284 (2010).

Dougherty R., Freiling C. & Zeger K., Achievable Rate Regions for Network Coding, IEEE Transactions on Information Theory, 2015; 61(5):2488-2509.

Dougherty R. & Zeger K., Non-reversibility and equivalent constructions of Multiple-Unicast Networks, IEEE Transactions on Information Theory, 2006; 52(11):5067-5077

Gadouleau M., Closure solvability for Network Coding and Secret Sharing, IEEE Trans. Inform. Theory, UK , 2013; 59(12):7858-7869.

Matús, F., Matroid representations by partitions, Discrete Math., 1999; 203:169-194.

Mejía C., On the theory of linear rank inequalities, Tesis de Doctorado, Universidad Nacional de Colombia, Bogotá. Disponible en red, 2016.

Oxley J. G., Matroid Theory, Oxford Graduate Text in Mathematics, Department of Mathematics, Louisiana State University, 1992.

Peña V., Conexiones entre codificación en red, operadores de clausura y matroides de secreto compartido, Tesis de Maestría, Universidad Nacional de Colombia, Bogotá. Disponible en red, 2015.

Peña V. & Sarria H., How to find new Characteristic-Dependent Linear Rank Inequalities using binary matrices as a guide, 2019; ar-Xiv:1905.00003.

Riis S. & Gadouleau M., Graph-theoretical constructions for graph entropy and network coding based communications, IEEE Transactions on Information Theory, 2011; 57(10):6703-6717.

Seymour P. D., On secret-sharing matroids, Journal of Combinatorial Theory, 1992; B(56):69-73.

Shamir A., How to share a secret, Communications of the ACM, 1979; 22(11):612-613.

Shen A., Hammer D., Romashchenko A. E. & Vereshchagin N. K., Inequalities for Shannon entropy and Kolmogorov complexity, Journal of Computer and Systems Sciences, 2000; 60:442-464.

Simonis J. & Ashikhmin A., Almost affine codes, Des. Codes Cryptogr. 1998; 14:179-197.

Published

2019-12-24

How to Cite

Peña-Macias, V., & Sarria, H. (2019). Linear Programming Problems in Network Coding and Closure Operators via Partitions. Selecciones Matemáticas, 6(02), 264-274. https://doi.org/10.17268/sel.mat.2019.02.12