Algoritmos para problemas de flujos indivisibles y juegos en árboles

Abstract

En esta memoria se enfrentan dos problemas. El primero de ellos es Unsplittable Flow on Trees, en el cual dados un árbol con capacidades G, un conjunto de flujos de distintos tamaños T' y un natural k, se busca encontrar un conjunto de k flujos que respeten las restricciones de capacidad de las aristas. La versión en que el grafo es un camino corresponde a un problema de scheduling. Para este problema se desarrollan algoritmos parametrizados. El segundo problema es Stackelberg MST completo. En StackMST hay dos jugadoras, una roja que posee un conjunto de aristas R que forman un árbol generador del grafo y tienen precios definidos, y una azul que posee un conjunto de aristas B a las cuales se debe asignar un precio, tras lo cual un ente externo selecciona un MST del grafo, y cada jugadora obtiene la suma de los precios de sus aristas que estén en el MST. El problema consiste en asignar precios a las aristas de la jugadora azul con tal de maximizar su utilidad. En la tesis enfrentamos la versión del problema en que (G,B \cup R) es un grafo completo, para la cual presentamos un algoritmo que en tiempo polinomial soluciona una restricción de este problema, el cual posteriormente es usado para construir un algoritmo (2ln(2)+epsilon)-aproximado.