Hay una -algoritmo competitivo para resolver el -Problema del servidor en un espacio métrico arbitrario?
El problema del servidor k es un problema de la informática teórica en la categoría de algoritmos en línea , uno de los dos problemas abstractos sobre espacios métricos que son fundamentales para la teoría del análisis competitivo (el otro son los sistemas de tareas métricas ). En este problema, un algoritmo en línea debe controlar el movimiento de un conjunto de k servidores , representados como puntos en un espacio métrico, y manejar las solicitudes.que también tienen forma de puntos en el espacio. A medida que llega cada solicitud, el algoritmo debe determinar qué servidor mover al punto solicitado. El objetivo del algoritmo es mantener pequeña la distancia total que se mueven todos los servidores, en relación con la distancia total que los servidores podrían haberse movido por un adversario óptimo que conoce de antemano toda la secuencia de solicitudes.
El problema fue planteado por primera vez por Mark Manasse , Lyle A. McGeoch y Daniel Sleator (1990). La pregunta abierta más importante con respecto al problema del servidor k es la llamada conjetura del servidor k , también planteada por Manasse et al. Esta conjetura establece que existe un algoritmo para resolver el problema del servidor k en un espacio métrico arbitrario y para cualquier número k de servidores que tenga una relación competitiva exactamente k . Manasse y col. pudieron 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) demostraron la conjetura para las métricas de árboles. El caso especial de métricas en las que todas las distancias son iguales se denomina problema de paginación porque modela el problema de los algoritmos de reemplazo de páginas en las memorias caché, y también se sabía que tenía un algoritmo competitivo k ( Sleator y Tarjan 1985). Fiat y col. (1990) primero demostró que existe un algoritmo con razón competitiva finita para cualquier constante ky cualquier espacio métrico, y finalmente Koutsoupias y Papadimitriou (1995) demostraron que el algoritmo de función de trabajo (WFA) tiene una razón competitiva 2 k - 1. Sin embargo, a pesar de Los esfuerzos de muchos otros investigadores, la reducción de la relación competitiva ak o proporcionar un límite inferior mejorado permanece abierto a partir de 2014 [actualizar]. El escenario más común que se cree es que el algoritmo de función de trabajo es k- competitivo. En esta dirección, en 2000 Bartal y Koutsoupias demostraron que esto es cierto para algunos casos especiales (si el espacio métrico es una línea, una estrella ponderada o cualquier métrica de k +2 puntos).
En 2011, se encontró un algoritmo aleatorio con límite competitivo Õ (log 2 k log 3 n). [1] [2] En 2017, se encontró un algoritmo aleatorio con límite competitivo O (log 6 k). [3]
Ejemplo
Para hacer el problema más concreto, imagine enviar técnicos de atención al cliente a los clientes cuando tienen problemas con sus equipos. En nuestro problema de ejemplo, hay dos técnicos, Mary y Noah, que atienden a tres clientes, en San Francisco, California; Washington DC; y Baltimore, Maryland. Como problema del servidor k , los servidores son los técnicos, entonces k = 2 y este es un problema de 2 servidores. Washington y Baltimore están a 56 km (35 millas) de distancia, mientras que San Francisco está a 4800 km (3,000 millas) de ambos, e inicialmente Mary y Noah están en San Francisco.
Considere un algoritmo para asignar servidores a las solicitudes que siempre asigne el servidor más cercano a la solicitud, y suponga que cada mañana de lunes a viernes el cliente en Washington necesita asistencia, mientras que cada tarde de lunes a viernes el cliente de Baltimore necesita asistencia y que el cliente de San Francisco nunca necesita asistencia. Luego, nuestro algoritmo asignará uno de los servidores (por ejemplo, Mary) al área de Washington, después de lo cual ella siempre será el servidor más cercano y siempre se asignará a todas las solicitudes de los clientes. Por lo tanto, todos los días nuestro algoritmo incurre en el costo de viajar entre Washington y Baltimore y viceversa, 70 millas (110 km). Después de un año de este patrón de solicitud, el algoritmo habrá incurrido en viajes de 20,500 millas (33,000 km): 3000 para enviar a Mary a la costa este y 17,500 para los viajes entre Washington y Baltimore. Por otro lado, un adversario óptimo que conozca el cronograma de solicitudes futuras podría haber enviado a Mary y Noah a Washington y Baltimore respectivamente, pagando 6,000 millas (9,700 km) de viaje una vez, pero luego evitando cualquier costo de viaje futuro. La relació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 relación competitiva de este algoritmo puede hacerse arbitrariamente grande.
Así vemos que asignar siempre el servidor más cercano puede estar lejos de ser óptimo. Por otro lado, parece una tontería que un algoritmo que no conoce las solicitudes futuras envíe a sus dos técnicos fuera de San Francisco, ya que la próxima solicitud podría estar en esa ciudad y tendría que enviar a alguien de regreso de inmediato. Por tanto, parece que es difícil o imposible que un algoritmo de servidor k funcione bien en relación con su adversario. Sin embargo, para el problema de 2 servidores existe un algoritmo que siempre tiene una distancia total de viaje de como máximo el doble de la distancia del adversario. La conjetura del servidor k establece que existen soluciones similares para problemas con un número mayor de técnicos.
Referencias
- Chrobak, Marek ; Larmore, Lawrence L. (1991). "Un algoritmo en línea óptimo para servidores K en árboles". Revista SIAM de Computación . 20 (1): 144-148. CiteSeerX 10.1.1.53.2395 . doi : 10.1137 / 0220008 .
- Fiat, A .; Rabani, Y .; Ravid, Y. (1990). " Algoritmos competitivos de servidor k ". Actas del 31º Simposio Anual del IEEE sobre Fundamentos de las Ciencias de la Computación . págs. 454–463.
- Koutsoupias, Elias; Papadimitriou, Christos H. (1995). "Sobre la conjetura del servidor k ". Revista de la ACM . 42 (5): 971–983. doi : 10.1145 / 210118.210128 .
- Manasse, Mark; McGeoch, Lyle A .; Sleator, Daniel D. (1990). "Algoritmos competitivos para problemas de servidor". Revista de algoritmos . 11 (2): 208–230. doi : 10.1016 / 0196-6774 (90) 90003-W .
- Sleator, Daniel D .; Tarjan, Robert E. (1985). "Eficiencia amortizada de actualización de lista y reglas de paginación". Comunicaciones de la ACM . 28 (2): 202-208. doi : 10.1145 / 2786.2793 .