Sistema de tareas métricas

Los sistemas de tareas son objetos matemáticos que se utilizan para modelar el conjunto de posibles configuraciones de algoritmos en línea . Fueron introducidos por Borodin , Linial y Saks (1992) para modelar una variedad de problemas en línea. Un sistema de tareas determina un conjunto de estados y costos para cambiar de estado. Los sistemas de tareas obtienen como entrada una secuencia de solicitudes de manera que cada solicitud asigna tiempos de procesamiento a los estados. El objetivo de un algoritmo en línea para sistemas de tareas es crear un cronograma que minimice el costo total incurrido debido al procesamiento de las tareas con respecto a los estados y debido al costo de cambiar de estado.

Si la función de costo para cambiar de estado es una métrica , el sistema de tareas es un sistema de tareas métricas (MTS). Este es el tipo más común de sistemas de tareas. Los sistemas de tareas métricas generalizan problemas en línea como la paginación , el acceso a listas y el problema del servidor k (en espacios finitos).

Definicion formal

Un sistema de tareas es un par donde es un conjunto de estados y es una función de distancia. Si es una métrica, es un sistema de tareas métrico. Una entrada al sistema de tareas es una secuencia tal que, para cada una , hay un vector de entradas no negativas que determinan los costos de procesamiento para los estados cuando se procesa la tarea.${\displaystyle (S,d)}$${\displaystyle S=\{s_{1},s_{2},\dotsc ,s_{n}\}}$${\displaystyle d:S\times S\rightarrow \mathbb {R} }$${\displaystyle d}$${\displaystyle (S,d)}$${\displaystyle \sigma =T_{1},T_{2},\dotsc ,T_{l}}$${\displaystyle i}$${\displaystyle T_{i}}$${\displaystyle n}$${\displaystyle n}$${\displaystyle i}$

Un algoritmo para el sistema de tareas produce un programa que determina la secuencia de estados. Por ejemplo, significa que la tarea se ejecuta en estado . El costo de procesamiento de un horario es${\displaystyle \pi }$${\displaystyle \pi (i)=s_{j}}$${\displaystyle i}$${\displaystyle T_{i}}$${\displaystyle s_{j}}$${\displaystyle \mathrm {cost} (\pi ,\sigma )=\sum _{i=1}^{l}d(\pi (i-1),\pi (i))+T_{i}(\pi (i)).}$

El objetivo del algoritmo es encontrar un cronograma tal que se minimice el costo.

Resultados conocidos

Como es habitual para los problemas en línea, la medida más común para analizar algoritmos para sistemas de tareas métricas es el análisis competitivo , donde el rendimiento de un algoritmo en línea se compara con el rendimiento de un algoritmo fuera de línea óptimo. Para los algoritmos deterministas en línea, existe un límite estricto en la relación competitiva debido a Borodin et al. (1992).${\displaystyle 2n-1}$

En el caso de los algoritmos en línea aleatorios, la relación competitiva está limitada por el límite inferior y por el límite superior por . El límite inferior se debe a Bartal et al. (2006, 2005). El límite superior se debe a Bubeck, Cohen, Lee y Lee (2018), quienes mejoraron el resultado de Fiat y Mendel (2003).${\displaystyle \Omega (\log n/\log \log n)}$${\displaystyle O\left((\log n)^{2}\right)}$

Hay muchos resultados para varios tipos de métricas restringidas.

Ver también

• Modelo adversario
• Análisis competitivo
• Problema del servidor K
• Algoritmo en línea
• Algoritmo de reemplazo de página
• Computación en tiempo real

Referencias

• Yair Bartal; Avrim Blum; Carl Burch y Andrew Tomkins (1997). "Un algoritmo polylog (n) -Competitive para sistemas de tareas métricas". Actas del Vigésimo Noveno Simposio Anual ACM sobre Teoría de la Computación . págs. 711–719. doi : 10.1145 / 258533.258667 .

• Yair Bartal, Béla Bollobás , Manor Mendel (2006). "Teoremas tipo Ramsey para espacios métricos con aplicaciones a problemas en línea". Revista de Ciencias de la Computación y Sistemas . 72 (5): 890–921. arXiv : cs / 0406028 . doi : 10.1016 / j.jcss.2005.05.008 .

• Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor (2005). "Sobre fenómenos métricos de tipo Ramsey". Annals of Mathematics . 162 (2): 643–709. arXiv : matemáticas / 0406353 . doi : 10.4007 / annals.2005.162.643 .

• Allan Borodin y Ran El-Yaniv (1998).Computación en línea y análisis competitivo. Prensa de la Universidad de Cambridge. págs. 123-149.
• Allan Borodin , Nati Linial y Michael Saks (1992). "Un algoritmo en línea óptimo para sistemas de tareas métricas". Revista de la ACM . 39 (4): 745–763. doi : 10.1145 / 146585.146588 .

• Amos Fiat y Manor Mendel (2003). "Mejores algoritmos para aplicaciones y sistemas de tareas métricas injustas". SIAM J. Comput . 32 (6): 1403-1422. arXiv : cs / 0406034 . doi : 10.1137 / S0097539700376159 .

• Sébastien Bubeck; Michael B. Cohen; James R. Lee y Yin Tat Lee (2019). "Sistemas de tareas métricas en árboles mediante descenso de espejos y pegado injusto". Actas del Trigésimo Simposio Anual ACM-SIAM sobre Algoritmos Discretos . arXiv : 1807.04404 .