Sistema de tareas métrico

Los sistemas de tareas son objetos matemáticos utilizados 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 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 un cronograma que minimice el costo total incurrido por el procesamiento de las tareas con respecto a los estados y el 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 métrico de tareas (MTS). 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 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 , hay un vector de entradas no negativas que determinan los costos de procesamiento para los estados al procesar la enésima 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 cronograma que determina la secuencia de estados. Por ejemplo, significa que la enésima tarea se ejecuta en estado . El costo de procesamiento de un cronograma 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 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 se compara el desempeño de un algoritmo en línea con el desempeño 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}$

Para los algoritmos en línea aleatorios, la relación competitiva tiene un límite inferior y un límite superior . 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). ${\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 competitivo polilog (n) para sistemas de tareas métricos". Actas del vigésimo noveno simposio anual de la ACM sobre teoría de la informática . págs. 711–719. doi : 10.1145/258533.258667 .

• Yair Bartal, Béla Bollobás , Señorío Mendel (2006). "Teoremas de tipo Ramsey para espacios métricos con aplicaciones a problemas en línea". Revista de Ciencias de la Computación y de Sistemas . 72 (5): 890–921. arXiv : cs/0406028 . doi : 10.1016/j.jcss.2005.05.008. S2CID  1450455.{{cite journal}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace )

• Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor (2005). "Sobre los fenómenos métricos de tipo Ramsey". Anales de Matemáticas . 162 (2): 643–709. arXiv : matemáticas/0406353 . doi : 10.4007/annals.2005.162.643.{{cite journal}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace )

• 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étricos". Revista de la ACM . 39 (4): 745–763. doi : 10.1145/146585.146588 . S2CID  18783826.{{cite journal}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace )

• Amos Fiat y Manor Mendel (2003). "Mejores algoritmos para aplicaciones y sistemas de tareas métricas injustas". SIAM J. Computación . 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 métricos de tareas en árboles mediante descenso de espejos y pegado injusto". Actas del trigésimo simposio anual ACM-SIAM sobre algoritmos discretos . arXiv : 1807.04404 .