Sesión Matemática Discreta y Teoría de JuegosUna caracterización poliédrica de los matchings cuasi-estables
Noelia Juarez
Universidad Nacional de San Luis - Instituto de Matemática Aplicada San Luis , Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
En el modelo clásico de matching uno a uno, un conjunto de firmas y un conjunto de trabajadores deben ser asignados mutuamente teniendo en cuenta sus preferencias. Un criterio fundamental en este contexto es la estabilidad, que exige la ausencia de pares bloqueantes. La noción de cuasi-estabilidad relaja esta condición al permitir pares bloqueantes únicamente cuando involucran a un trabajador no asignado. En este trabajo estudiamos la estructura poliédrica del conjunto de matchings cuasi-estables del lado de los trabajadores. A partir de la caracterización de Rothblum [1] del politopo de los matchings estables, proponemos una relajación de las restricciones de estabilidad que describe esta nueva clase de soluciones. Demostramos que los puntos enteros del politopo resultante corresponden exactamente a esta clase de matchings. Esta caracterización proporciona una formulación mediante programación lineal del problema y ofrece una nueva perspectiva geométrica para el estudio de la cuasi-estabilidad. Los resultados obtenidos constituyen un primer paso hacia el análisis de problemas de optimización sobre esta clase más amplia de matchings.
Trabajo en conjunto con: Guiñazú, Nadia (UNSL - IMASL), Manasero, Paola Belén (UNSL - IMASL), Neme, Pablo (UNSL - IMASL) y Oviedo, Jorge (UNSL - IMASL).
Referencias
[1] Rothblum, U. G. (1992). Characterization of stable matchings as extreme points of a polytope. Mathematical Programming, 54, 57–67.