La asignación de rango máximo (RM) es una regla para la división justa de elementos indivisibles. Supongamos que tenemos que distribuir algunos elementos entre personas. Cada persona puede clasificar los elementos de mejor a peor. La regla de RM dice que tenemos que dar a la mayor cantidad de personas posible su mejor artículo (n. ° 1). Sujeto a eso, tenemos que dar a la mayor cantidad posible de personas su siguiente mejor elemento (n. ° 2), y así sucesivamente.
En el caso especial en el que cada persona debería recibir un solo elemento (por ejemplo, cuando los "elementos" son tareas y cada tarea debe ser realizada por una sola persona), el problema se denomina coincidencia de rango máximo o coincidencia codiciosa .
La idea es similar a la del corte de pasteles utilitario , donde el objetivo es maximizar la suma de utilidades de todos los participantes. Sin embargo, la regla utilitaria funciona con funciones de utilidad cardinales (numéricas) , mientras que la regla RM funciona con utilidades ordinales (clasificaciones).
Definición
Hay varios artículos y varios agentes. Cada agente tiene un pedido total de los artículos. Los agentes pueden mostrarse indiferentes entre algunos elementos; para cada agente, podemos dividir los elementos en clases de equivalencia que contienen elementos del mismo rango. Por ejemplo, si la relación de preferencias de Alice es x> y, z> w , significa que la primera opción de Alice es x, que es mejor para ella que todos los demás elementos; La segunda opción de Alice es y y z, que son igualmente buenas a sus ojos pero no tan buenas como x; y la tercera opción de Alice es w, que considera peor que todos los demás elementos.
Para cada asignación de elementos a los agentes, construimos su vector de rango de la siguiente manera. El elemento n. ° 1 en el vector es el número total de elementos que son la primera opción para sus propietarios; El elemento n. ° 2 es el número total de elementos que son la segunda opción para sus propietarios; y así.
Una asignación de rango máximo es aquella en la que el vector de rango es máximo (en orden lexicográfico).
Ejemplo
Tres elementos, xy y z, deben dividirse entre tres agentes cuyas clasificaciones son:
- Alice: x> y> z
- Bob: x> y> z
- Carl: y> x> z
En la asignación ( x , y , z ), Alice obtiene su primera opción ( x ), Bob obtiene su segunda opción ( y ) y Carl obtiene su tercera opción ( z ). Por tanto, el vector de rango es (1,1,1).
En la asignación ( x , z , y ), tanto Alice como Carl obtienen su primera opción y Bob obtiene su tercera opción. Por lo tanto, el vector de rango es (2,0,1), que es lexicográficamente más alto que (1,1,1), lo que da a más personas su primera opción.
Es fácil comprobar que ninguna asignación produce un vector de rango lexicográficamente más alto. Por tanto, la asignación ( x , z , y ) es de rango máximo. De manera similar, la asignación ( z , x , y ) es de rango máximo: produce el mismo vector de rango (2,0,1).
Algoritmos
Los emparejamientos de RM fueron estudiados por primera vez por Robert Irving, quien los llamó emparejamientos codiciosos . Presentó un algoritmo que encuentra una coincidencia de RM en el tiempo, donde n es el número de agentes yc es la mayor longitud de una lista de preferencias de un agente. [1]
Más tarde, se encontró un algoritmo mejorado, que se ejecuta en el tiempo , donde m es la longitud total de todas las listas de preferencias (número total de bordes en el gráfico), y C es el rango máximo de un elemento utilizado en una coincidencia de RM (es decir, el número máximo de elementos distintos de cero en un vector de rango). [2]
Una solución diferente, que utiliza emparejamientos de peso máximo , logra un tiempo de ejecución similar:. [3]
Variantes
El problema tiene varias variantes.
1. En el emparejamiento RM de cardinalidad máxima , el objetivo es encontrar, entre todos los emparejamientos de RM diferentes, el que tenga el número máximo de emparejamientos.
2. En el emparejamiento justo , el objetivo es encontrar un emparejamiento de cardinalidad máxima tal que se use el número mínimo de bordes de rango r , dado que - se usa el número mínimo de bordes de rango r −1, y así sucesivamente.
Tanto la coincidencia de RM de cardinalidad máxima como la coincidencia justa se pueden encontrar reduciendo a la coincidencia de peso máximo. [3]
3. En el problema de emparejamiento de RM capacitado , cada agente tiene una capacidad superior que indica un límite superior en el número total de artículos que debe obtener. Cada artículo tiene una cuota superior que indica un límite superior en el número de agentes diferentes a los que puede asignarse. Fue estudiado por primera vez por Melhorn y Michail, quienes dieron un algoritmo con tiempo de ejecución. [4] Hay un algoritmo mejorado con tiempo de ejecución., donde B es el mínimo de la suma de cuotas de los agentes y la suma de cuotas de los artículos. Se basa en una extensión de la descomposición de Gallai-Edmonds a coincidencias de múltiples bordes. [5]
Ver también
Referencias
- ^ Irving, Robert W. (2003). Emparejamientos codiciosos . Universidad de Glasgow. págs. Tr – 2003–136. CiteSeerX 10.1.1.119.1747 .
- ^ Irving, Robert W .; Kavitha, Telikepalli; Mehlhorn, Kurt; Michail, Dimitrios; Paluch, Katarzyna E. (1 de octubre de 2006). "Coincidencias de rango máximo". ACM Trans. Algoritmos . 2 (4): 602–610. doi : 10.1145 / 1198513.1198520 . ISSN 1549-6325 .
- ^ a b Michail, Dimitrios (10 de diciembre de 2007). "Reducción de la coincidencia de peso de rango máximo a máximo". Informática Teórica . 389 (1): 125-132. doi : 10.1016 / j.tcs.2007.08.004 . ISSN 0304-3975 .
- ^ Kurt Mehlhorn y Dimitrios Michail (2005). "Problemas de red con aplicaciones y pesos no polinomiales" .
- ^ Paluch, Katarzyna (22 de mayo de 2013). Coincidencias de rango máximo capacitado . Algoritmos y complejidad . Apuntes de conferencias en informática. 7878 . Springer, Berlín, Heidelberg. págs. 324–335. doi : 10.1007 / 978-3-642-38233-8_27 . ISBN 978-3-642-38232-1.