Asignación Óptima en Sistemas Discretos

 Pareo de Elementos

El problema de parear elementos de un conjunto con otro conjunto, conocido formalmente como matching, es un problema clásico de la teoría de grafos con aplicaciones vastas en la ingeniería de sistemas. En su forma más común, el pareo en grafos bipartitos,

buscamos encontrar el mayor número posible de aristas que no compartan un nodo común, entre dos conjuntos de nodos distintos.

Ejemplos de aplicaciones en ingeniería de sistemas incluyen:

• Asignación de tareas a procesadores: Emparejar las tareas más adecuadas con los procesadores disponibles para optimizar el rendimiento.

• Asignación de recursos en la nube: Parear contenedores o máquinas virtuales con nodos de cómputo físicos de manera eficiente.

• Planificación de horarios: En sistemas de gestión de proyectos, asignar equipos a proyectos específicos.

• Problemas de emparejamiento en sistemas distribuidos: Como la asignación de peticiones a servicios, o la conexión de clientes a servidores cercanos.

Sorprendentemente, un problema de pareo máximo en un grafo bipartito puede transformarse en un problema de flujo máximo. Se construye una red auxiliar con una fuente conectada a un conjunto de nodos, un sumidero conectado al otro conjunto, y aristas de capacidad unitaria entre los nodos que pueden ser emparejados. El flujo máximo en esta red corresponderá al tamaño del pareo máximo.