| Sumario: | En este trabajo desarrollamos la teoría necesaria para el estudio del algoritmo de entrada
secuencial, con el fin de analizar la relación entre el orden en el que entran los individuos en la aplicación del algoritmo y el matching que se obtiene como salida de dicho algoritmo.
El trabajo está organizado en tres secciones. En la primera sección introducimos las definiciones básicas acerca de la teoría de matching y ejemplificamos algunas de ellas. En particular, definimos el concepto de ciclo y el de matching cuasi-estable, y proporcionamos la demostración de algunos resultados que son muy útiles en el estudio del algoritmo de aceptación diferida con matching de entrada arbitrario.
En la segunda sección estudiamos dicho algoritmo y demostramos que si el matching de entrada es cuasi-estable, el matching obtenido como salida del algoritmo resulta estable. En la tercera sección describimos el algoritmo de entrada secuencial y estudiamos el concepto de orden óptimo y los resultados obtenidos por Millán.
Proponemos ejemplos que permiten observar que la condición de orden óptimo no resulta
necesaria para la obtención del matching óptimo como salida del algoritmo de entrada
secuencial
|
|---|
Biblioteca Digital de Vanguardia