Sistema de tareas métricas

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

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

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

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

El objetivo del algoritmo es encontrar una programación que minimice el coste.

Como es habitual en 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 algoritmos en línea deterministas, existe una cota ajustada.${\displaystyle 2n-1}$sobre la relación competitiva según Borodin et al. (1992).

Para los algoritmos en línea aleatorios, la razón competitiva está limitada inferiormente por${\displaystyle \Omega (\log n/\log \log n)}$y limitado superiormente por${\displaystyle O\left((\log n)^{2}\right)}$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 un resultado de Fiat y Mendel (2003).

Existen numerosos resultados para diversos tipos de métricas restringidas.

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

• Yair Bartal; Avrim Blum; Carl Burch y Andrew Tomkins (1997). "Un algoritmo competitivo polilog(n) para sistemas de tareas métricas". Actas del vigésimo noveno simposio anual de la ACM sobre la 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 de tipo Ramsey para espacios métricos con aplicaciones a problemas en línea". Journal of Computer and System Sciences . 72 (5): 890– 921. arXiv : cs/0406028 . doi : 10.1016/j.jcss.2005.05.008 . S2CID 1450455 . {{cite journal}}: CS1 maint: varios nombres: lista de autores ( enlace )

• 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 : math/0406353 . doi : 10.4007/annals.2005.162.643 .{{cite journal}}: CS1 maint: varios nombres: lista de autores ( enlace )

• Allan Borodin y Ran El-Yaniv (1998).Computación en línea y análisis competitivo. Cambridge University Press. págs. 123–149 . 
• Allan Borodin , Nati Linial y Michael Saks (1992). "Un algoritmo óptimo en línea para sistemas de tareas métricas" . Journal of the ACM . 39 (4): 745–763 . doi : 10.1145/146585.146588 . S2CID 18783826 . {{cite journal}}: CS1 maint: varios nombres: lista de autores ( enlace )

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

• Bubeck, Sébastien; Cohen, Michael B.; R. Lee, James y Lee, Yin Tat (2019). "Sistemas de tareas métricas en árboles mediante descenso por espejo y pegado injusto". Actas del trigésimo simposio anual ACM-SIAM sobre algoritmos discretos . arXiv : 1807.04404 .