El protocolo Edmonds-Pruhs es un protocolo para un corte de pastel justo . Su objetivo es crear una división parcialmente proporcional de un recurso heterogéneo entre n personas, de modo que cada persona reciba un subconjunto del pastel que esa persona valora como al menos 1 / an del total, dondees una constante suficientemente grande. Es un algoritmo aleatorio cuyo tiempo de ejecución es O ( n ) con probabilidad cercana a 1. El protocolo fue desarrollado por Jeff Edmonds y Kirk Pruhs , quienes luego lo mejoraron en trabajo conjunto con Jaisingh Solanki .
Motivación
Se puede lograr una división proporcional de un pastel utilizando el algoritmo recursivo de reducción a la mitad en el tiempo O ( n log n ). Varios resultados de dureza muestran que este tiempo de ejecución es óptimo bajo una amplia variedad de supuestos. En particular, la reducción a la mitad recursiva es el algoritmo más rápido posible para lograr la proporcionalidad total cuando las piezas deben ser contiguas, y es el algoritmo determinista más rápido posible para lograr una proporcionalidad incluso parcial e incluso cuando las piezas pueden desconectarse. Un caso que no está cubierto por los resultados de dureza es el caso de los algoritmos aleatorizados , que garantizan solo una proporcionalidad parcial y con piezas posiblemente desconectadas . El protocolo Edmonds-Pruhs tiene como objetivo proporcionar un algoritmo con tiempo de ejecución O ( n ) para este caso.
El protocolo
El esquema general es el siguiente: [1]
- Los tabiques de cada socio privado la torta a una piezas de igual valor subjetivo. Estas piezas n ⋅ an se denominan piezas candidatas .
- Cada socio elige 2 d piezas candidatas uniformemente al azar, con reemplazo ( d es una constante que se determinará más adelante). Los candidatos se agrupan en d pares, que el socio informa al algoritmo. Estos n⋅d pares se denominan paréntesis de cuartos de final .
- De cada paréntesis de cuartos de final, el algoritmo selecciona una sola pieza: la pieza que se cruza con la menor cantidad de otras piezas candidatas. Estas n ⋅ d piezas se denominan piezas semifinales .
- Para cada socio, el algoritmo selecciona una sola pieza; se llaman piezas finales . Las piezas finales se seleccionan de manera que cada punto de la torta esté cubierto por un máximo de 2 piezas finales (ver más abajo). Si tiene éxito, continúe con el paso 5. Si esto falla, comience de nuevo en el paso # 1.
- Cada parte del pastel que pertenece a una única pieza final, se entrega al propietario de esa pieza. Cada parte del pastel que pertenece a dos piezas finales, se divide proporcionalmente por cualquier algoritmo de división proporcional determinista.
El algoritmo garantiza que, con alta probabilidad, cada socio recibe al menos la mitad de una de sus piezas candidatas, lo que implica (si los valores son aditivos) un valor de al menos 1/2 an .
Hay O ( n ) piezas candidatas y O ( n ) divisiones adicionales en el paso # 5, cada una de las cuales toma O (1) tiempo. Por tanto, el tiempo de ejecución total del algoritmo es O ( n ).
El principal desafío en este esquema es seleccionar las piezas finales en el paso # 4:
Empiece por crear el gráfico de implicación : un gráfico cuyos nodos son las piezas semifinales, y hay una arista de la pieza I del socio i a la pieza J del socio j si la pieza I se cruza con la otra pieza del socio j (por lo tanto, si seleccionamos la pieza Yo y quiero evitar la intersección, deberíamos seleccionar la pieza J también).
Seleccione un socio arbitrario i que aún no haya recibido una pieza y seleccione una pieza arbitraria I de ese socio como pieza final. A continuación, atravesar los enlaces en el gráfico y seleccione implicación como piezas finales todas las piezas que son accesibles desde I . Hay dos buenos escenarios: o asignamos una única pieza final a cada socio y terminamos, o llegamos a una pieza sin enlaces salientes (lo que implica que no se cruza con otras piezas). En el último caso, simplemente elegimos otra pieza de uno de los socios restantes y continuamos. El mal escenario es que nuestro recorrido nos lleva a dos partes diferentes de la misma pareja, o lo que es lo mismo, a la otra parte de la pareja i de la que partimos. Una ruta de este tipo, que va de una parte del socio i a otra parte del mismo socio, se denomina ruta de pareja . Si el gráfico de implicaciones no contiene rutas de pares, entonces el algoritmo de selección que se acaba de describir devuelve una colección de n piezas finales que no se superponen y ya está. Ahora queda calcular la probabilidad de que el gráfico de implicaciones contenga una ruta de par.
Primero, considere el caso especial en el que todos los socios tienen la misma función de valor (y, por lo tanto, la misma colección de piezas candidatas). En este caso, la probabilidad de una ruta de par es fácil de calcular: dado que la probabilidad de cada borde es 1 / an , y todas las aristas son independientes, la probabilidad de una ruta de par específica de longitud k es 1 / ( an ) k , y la probabilidad de cualquier ruta de par es como máximo:
Al seleccionar d = 1 y una suficientemente grande, es posible hacer que esta probabilidad tan pequeña como que queremos. Esto es cierto incluso si omitimos la fase de selección de semifinales (# 3) y simplemente tomamos todas las piezas de cuartos de final como semifinales.
Tenga en cuenta que este caso es análogo al modelo de bolas en contenedores . Demuestra que, si se seleccionan d contenedores al azar para cada bola, entonces es posible seleccionar un contenedor para cada bola de manera que todos los contenedores sean distintos (la carga máxima es 1).
En el modelo de torta general, donde las funciones de valor son diferentes, las probabilidades de los bordes en el gráfico de implicaciones son dependientes. pero gracias a la fase de selección semifinal, podemos probar que la probabilidad de que el gráfico de implicaciones contenga una ruta de par de longitud al menos 3 es como máximo.
Queda por manejar caminos de pares de longitud 2. Desafortunadamente, la probabilidad de tener tales caminos de pares en el gráfico de implicaciones no es despreciable. Sin embargo, con alta probabilidad es posible dividir a los socios en dos grupos, de modo que en cada grupo no haya una ruta de par de longitud 2. Por lo tanto, podemos ejecutar el algoritmo de selección de la pieza final dos veces: una para cada grupo. La intersección solo puede ocurrir entre las piezas finales de diferentes grupos; por lo tanto, la superposición en cada punto de la torta es como máximo 2. La probabilidad de que tal división en 2 no sea posible es como máximo.
Al sumar las dos expresiones anteriores y establecer d = 2, obtenemos que la probabilidad de falla sigue siendo. Recuerde que a es la relación de proporcionalidad: cuanto más valor queremos garantizar a cada socio, más probable es que la división falle y tengamos que empezar de nuevo en el paso n. ° 1.
El mismo algoritmo funciona también cuando los cortes son aproximados, es decir, los socios no saben marcar piezas con exactamente el mismo valor; pueden marcar una pieza con un valor de p por ciento por encima o por debajo del valor requerido, donde el error exacto se elige al azar. [1]
Un protocolo de alta confianza
Es posible reducir aún más la probabilidad de falla utilizando el siguiente esquema: [2]
- Realice dos ejecuciones independientes del protocolo original.
- En cada ejecución, elimine todos los socios que aparecen al comienzo de una ruta de pares y asigne las piezas finales solo a los socios restantes como en el protocolo original.
- Si por cada socio hay al menos una carrera en la que no se elimina, entonces habremos terminado, ya que cada socio ahora tiene al menos una pieza final.
La probabilidad de eliminar a un compañero específico en cada ejecución es . La probabilidad de eliminar a un socio específico en ambas carreras es. Por lo tanto, la probabilidad de falla es, que va a 0 cuando n aumenta, incluso cuando la razón de proporcionalidad parcial a se mantiene constante.
Problemas relacionados
El modelo de pastel puede verse como una generalización de las bolas en el modelo de contenedores . Este modelo ha encontrado amplias aplicaciones en áreas como el equilibrio de carga . En estas situaciones, una pelota representa un trabajo que puede asignarse a varios contenedores / máquinas. En términos generales, el equilibrio de carga de máquinas idénticas es para bolas y recipientes, como el equilibrio de carga en máquinas no relacionadas es para cortar pasteles. Por lo tanto, es razonable que el modelo de torta y el protocolo de Edmonds-Pruhs tengan aplicaciones interesantes en entornos que involucran el equilibrio de carga en máquinas no relacionadas. [1]
Referencias
- ^ a b c Jeff Edmonds; Kirk Pruhs (2006). Asignaciones equilibradas de pastel . 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06) . pag. 623. doi : 10.1109 / focs.2006.17 . ISBN 978-0-7695-2720-8.
- ^ Jeff Edmonds; Kirk Pruhs; Jaisingh Solanki (2008). Cortar con confianza un pastel en pedazos aproximadamente justos . Apuntes de conferencias en Ciencias de la Computación. 5034 . págs. 155-164. CiteSeerX 10.1.1.145.8396 . doi : 10.1007 / 978-3-540-68880-8_16 . ISBN 978-3-540-68865-5.