Problemas de emparejamiento

Abstract

[ES] A lo largo de esta memoria estudiaremos las distintas variantes del problema de emparejamiento y veremos algunas de sus aplicaciones prácticas. Incluimos una amplia introducción, en la que constan varios resultados sobre redes con flujo y algoritmos para resolver distintas versiones de problemas de optimización ya conocidos, que nos servirán de herramienta para el tema que nos ocupa. Este estudio incluirá resultados teóricos, como el teorema del camino aumentador, que nos permitirán presentar algoritmos especialmente diseñados para la resolución de los problemas de emparejamiento.

[EN] In this paper we will study the different versions of the matching problem and we will show some of its practical applications. We include a wide introduction, in which there are several results about network flows and algorithms that solve various of the already known optimization problems, and will be a useful tool to the topic we are dealing with. We will include some theorical results, like the augmenting path theorem, that allow us to introduce some algorithms specially designed for matching problems.