Linear Programming Problems in Network Coding and Closure Operators via Partitions
DOI:
https://doi.org/10.17268/sel.mat.2019.02.12Keywords:
Directed graph, network code, closure operator, representable matroid, linear rank inequalityAbstract
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
How to Cite
Issue
Section
License
The authors who publish in this journal accept the following conditions:
1. The authors retain the copyright and assign to the journal the right of the first publication, with the work registered with the Creative Commons Attribution License,Atribución 4.0 Internacional (CC BY 4.0) which allows third parties to use what is published whenever they mention the authorship of the work And to the first publication in this magazine.
2. Authors may make other independent and additional contractual arrangements for non-exclusive distribution of the version of the article published in this journal (eg, include it in an institutional repository or publish it in a book) provided they clearly state that The paper was first published in this journal.
3. Authors are encouraged to publish their work on the Internet (for example, on institutional or personal pages) before and during the review and publication process, as it can lead to productive exchanges and to a greater and more rapid dissemination Of the published work.
