Problema k-server

El problema k-server es un problema de teoría de la ciencia de la computación en la categoría de algoritmos en línea, uno de dos problemas abstractos en espacios métricos que es central a la teoría de análisis competitivo (el otro es sistemas de tarea métrica). En este problema, un algoritmo en línea tiene que controlar el movimiento de un conjunto de k servidores, representados como puntos en un espacio métrico, y manejar peticiones que están también en la forma de puntos en el espacio. Cuando cada petición llega, el algoritmo tiene que determinar qué servidor mover al punto pedido. El objetivo del algoritmo es mantener la distancia total de todos los movimientos de los servidores pequeña, relativa a la distancia total que los servidores se podrían haber movido por un adversario óptimo quien sabe por adelantado la secuencia entera de peticiones.

El problema fue presentado por Mark Manasse, Lyle Un. McGeoch Y Daniel Sleator (1990). La cuestión abierta más prominente respecto del problema k-server es la llamada cojetura k-server, también presentado por Manasse, McGeoch y Sleator. Esta conjetura declara que hay un algoritmo para solucionar el problema k-server en un espacio métrico arbitrario y para cualquier número k de servidores que tiene proporción competitiva al menos k. Manasse, McGeoch y Sleator fueron capaces de probar su conjetura cuando k = 2, y para valores más generales de k cuando el espacio métrico está restringido para tener exactamente k+1 puntos. Chrobak y Larmore (1991) probaron la conjetura para la métrica (norma) de árbol. El caso especial de métrica (norma) en que todas distancias son iguales es llamado el problema de paginación porque modela el problema de algoritmos de sustitución de página en cachés de memoria, y era también ya sabido tener un algoritmo k-competitivo (Sleator y Tarjan 1985). Manasse, McGeoch y Sleator (1990) probaron que existe un algoritmo con proporción competitiva finita para cualquier constante k y cualquier espacio métrico, y finalmente Koutsoupias y Papadimitriou (1995) probaron que el algoritmo Work Function (WFA) tiene proporción competitiva 2k - 1. Aun así, a pesar de los esfuerzos de muchos otros investigadores, reduciendo la proporción competitiva a k o proporcionando una cota inferior mejorada, se mantiene aun abierto. El escenario creído más común es que el WFA es k-competitivo. Respecto a esto, en el año 2000 Bartal y Koutsoupias mostraron que esto es cierto para algunos casos especiales (si el espacio métrico es una línea, una estrella ponderada o cualquier métrica (norma) de k+2 puntos).

En 2011, se encontró un algoritmo aleatorio de costo Õ(log²k log³n).​

Ejemplo

Para hacer el problema más concreto, imagina enviar técnicos de soporte del cliente a clientes cuando tienen problema con su equipamiento. En nuestro problema de ejemplo hay dos técnicos, Mary y Noah, sirviendo tres clientes, en San Francisco, California; Washington D. C.; y Baltimore, Maryland. Como en el problema k-server, los servidores son los técnicos, por lo que k = 2 y esto es un problema 2-server. Washington y Baltimore están a 35 millas (56 km) de distancia, mientras San Francisco está a 3,000 millas (4,800 km) de ambos, e inicialmente Mary y Noah están ambos en San Francisco.

Considerar un algoritmo para asignar servidores a peticiones que siempre asigna el servidor más cercano a la petición, y suponer que cada día en la mañana el cliente en Washington necesita asistencia mientras cada día en la tarde el cliente en Baltimore necesita asistencia, y que el cliente en San Francisco nunca necesita asistencia. Entonces, nuestro algoritmo asignará uno de los servidores (por ejemplo Mary) al área de Washington, después de la cual siempre será el servidor más cercano y siempre será asignado a todas peticiones de cliente. Así, todos los días nuestro algoritmo incurre el costo de viajar entre Washington y Baltimore de ida y vuelta, 70 millas (110 km). Después de un año de este patrón de petición, el algoritmo habrá incurrido 20,500 millas (33,000 km) de viaje: 3000 para enviar Mary a la Costa Este, y 17,500 para los viajes entre Washington y Baltimore. Por otro lado, un adversario óptimo que sabe el programa de petición futuro podría haber enviado ambas Mary y Noah a Washington y Baltimore respectivamente, pagando 6,000 millas (9,700 km) de viajar una vez pero entonces evitando cualesquier costes de viaje futuros. La proporción competitiva de nuestro algoritmo en esta entrada es 20,500/6000 o aproximadamente 3.4, y ajustando los parámetros de este ejemplo la proporción competitiva de este algoritmo puede ser hecha arbitrariamente grande.

Por ello vemos que siempre asignando el servidor más cercano puede distar mucho de la solución optimal. Por otro lado, parece tonto para un algoritmo que no sabe peticiones futuras enviar uno de sus técnicos fuera de San Francisco, cuando la petición próxima podría ser en aquella ciudad y tendrían que enviar alguien de regreso inmediatamente. Por lo tanto, parece que es difícil o imposible para un algoritmo k-server actuar bien relativo a su adversario. Aun así, para el problema 2-server existe un algoritmo que siempre tiene una distancia de viaje total de como máximo dos veces la distancia del adversario. La conjetura k-server declara que las soluciones similares existen para problemas con cualquier número grande de técnicos.

Referencias

• Chrobak, Marek; Larmore, Lawrence L. (1991). «An optimal on-line algorithm for K-servers on trees». SIAM Journal on Computing 20 (1): 144-148. doi:10.1137/0220008. 

• Fiat, A.; Rabani, Y.; Ravid, Y. (1990). «Competitive k-server algorithms». Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science. pp. 454-463. 

• Koutsoupias, Elias; Papadimitriou, Christos H. (1995). «On the k-server conjecture». Journal of the ACM 42 (5): 971-983. doi:10.1145/210118.210128. 

• Manasse, Mark; McGeoch, Lyle A.; Sleator, Daniel D. (1990). "Competitive algorithms for server problems". Journal of Algorithms 11 (2): 208–230. doi:10.1016/0196-6774(90)90003-W. 

• Sleator, Daniel D.; Tarjan, Robert E. (1985). «Amortized efficiency of list update and paging rules». Communications of the ACM 28 (2): 202-208. doi:10.1145/2786.2793. 

• Datos: Q6322866