Nuevos algoritmos y mejoras computacionales para problemas de flujos en redes

  1. Antonio Sedeño Noda
Supervised by:
  1. Carlos González Martín Director

Defence university: Universidad de La Laguna

Year of defence: 2000

Committee:
  1. Francisco José Cano Sevilla Chair
  2. David Alcaide López de Pablo Secretary
  3. Miguel Sánchez García Committee member
  4. José Manuel Méndez Pérez Committee member
  5. Joaquín Sicilia Rodríguez Committee member
Department:
  1. Matemáticas, Estadística e Investigación Operativa

Type: Thesis

Abstract

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