Nuevos algoritmos y mejoras computacionales para problemas de flujos en redes

Resumo

La memoria se dedica al estudio de distintos problemas de Flujos en Redes, atendiendo a las vertientes algorítmica y computacional, El primer capítulo es introductorio y prepara el camino para desarrollos posteriores. En el se formalizan los distintos problemas generales en el ámbito de flujos en redes. También, se introducen distintas medidas, teóricas y experimentales, para estimar la bondad de los algoritmos en la práctica. En el segundo capítulo, dedicado al problema de flujo máximo, se realiza un experimento computacional para comparar el comportimiento empírico de un numeroso grupo de algoritmos, en el que se utilizan herramientas estadísticas. Este experimento permite idear dos nuevos algoritmos para el problema que reducen la complejidad computacional bajo la consideración de ciertas hipótesis. El tercer capítulo se dedica a distintos problemas de Biflujo Máximo. Para ello se realiza una formulación equivalente de dicho problema que permite por un lado demostrar de manera alternativa el teorema de Biflujo-Máximo Bicorte-Mínimo y por otor, idear un nuevo algoritmo cuyo esfuerzo computacional es O(nmlogU). También, se formaliza y se resuelve le problema de Biflujo Máximo simétrico en el mismo esfuerzo computacional. Finalmente en este capítulo, se caracteriza el conjunto de soluciones eficientes del problema de Biflujo Máximo Biobjetivo tanto en el espacio de decisiones como en el espacio de objetivos. Finalmente, en el cuarto capítulo se introduce y resuelve el problema de Flujo de Mínimo Coste Biobjetivo. En este caso se distingue si las variables que representan los flujos han de tomar valores enteros o no. El primer caso es denominado problema FRB y el segundo problema FERB.Para el problema FRB se proponen dos algoritmos para caracterizar el conjunto de soluciones eficientes extremas en el espacio objetivo. Los lagoritmos difieren en cuanto a las métricas usadas en el correspondiente problema auxi