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

Victor Peña Macias, Humberto Sarria Zapata

• 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.