Análisis determinista de problemas en emparejamiento en línea en los que se permiten aumentaciones

Abstract

El objetivo principal de este trabajo de tesis es estudiar una familia de extensiones del problema de emparejamientos en línea: Dado un grafo bipartito G = (L,R,E) donde el lado izquierdo es conocido mientras que el lado derecho llega en línea en un orden predeterminado y desconocido, cada vértice de R solo puede emparejarse en el momento que llega y el objetivo es construir el emparejamiento de mayor tamaño posible. Este problema fue introducido y estudiado por Karp, Vazirani y Vazirani [4], quienes construyen un algoritmo aleatorio que logra en esperanza una 1 − 1 e aproximación sobre cualquier instancia. En este trabajo se estudian variaciones de este problema en las cuales, al recibir un vértice del lado en línea j ∈R, el emparejamiento construido hasta ese momento puede ser aumentado con un camino aumentante comenzando en j de hasta un cierto largo. Se estudia además una familia de problemas en donde se impone un límite al número de veces que cada vértice puede ser reasignado.