Problemas de Programación Lineal en Redes de Información y Operadores de Clausura usando Particiones

• Peña-Macias, Victor ^[1] ; Sarria, Humberto ^[1]
  1. [1] Universidad Nacional de Colombia

     Universidad Nacional de Colombia

     Colombia

     
• Localización: Selecciones Matemáticas, ISSN-e 2411-1783, Vol. 6, Nº. 2, 2019 (Ejemplar dedicado a: Agosto-Diciembre), págs. 264-274
• Idioma: español
• DOI: 10.17268/sel.mat.2019.02.12
• Títulos paralelos:
  • Linear Programming Problems in Network Coding and Closure Operators via Partitions
• Enlaces
  • Texto completo (pdf)
• Resumen
  • español

    Una red de información es un grafo dirigido acíclico en el cual ciertos nodos llamados fuentes tienen mensajes que desean transmitir a otros nodos llamados receptores a través de la combinación de mensajes en nodos intermedios.El problema de solubilidad consiste en encontrar una colección adecuada de funciones que permita combinar los mensajes en los nodos intermedios para que puedan ser decodificados donde son requeridos. En esta trabajo se estudia el problema de solubilidad fraccional de una red a través de una extensión del problema de solubilidad de un operador de clausura definido por Gadouleau en el 2013. Se definen problemas de programación lineal mediante dicha conexión con operadores de clausura para estudiar la capacidad de una red; usando algunas desigualdades de la información y desigualdades rango lineales dependientes de la característica se obtienen cotas superiores sobre la capacidad lineal de algunas redes y operadores de clausura sobre un cuerpo dado.

  • English

    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.

• Referencias bibliográficas
  • 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...
  • 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,...
  • Dougherty R., Freiling C. & Zeger K., Networks, Matroids, and non-Shannon Information Inequalities, IEEE Trans. on Information Theory,...
  • 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...
  • 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...
  • 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...
  • 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...
  • Simonis J. & Ashikhmin A., Almost affine codes, Des. Codes Cryptogr. 1998; 14:179-197.