Sistema de tarefa métrica - Metrical task system

Os sistemas de tarefas são objetos matemáticos usados ​​para modelar o conjunto de configurações possíveis de algoritmos online . Eles foram introduzidos por Borodin , Linial e Saks (1992) para modelar uma variedade de problemas online. Um sistema de tarefas determina um conjunto de estados e custos para alterar estados. Os sistemas de tarefas obtêm como entrada uma sequência de solicitações, de modo que cada solicitação atribui tempos de processamento aos estados. O objetivo de um algoritmo online para sistemas de tarefas é criar uma programação que minimize o custo geral incorrido devido ao processamento das tarefas em relação aos estados e devido ao custo para alterar estados.

Se a função de custo para alterar estados é uma métrica , o sistema de tarefas é um sistema de tarefas métricas (MTS). Este é o tipo mais comum de sistemas de tarefas. Os sistemas de tarefas métricas generalizam problemas online, como paginação , acesso à lista e o problema do servidor k (em espaços finitos).

Definição formal

Um sistema de tarefas é um par onde é um conjunto de estados e é uma função de distância. Se é uma métrica, é um sistema de tarefa métrica. Uma entrada para o sistema de tarefas é uma sequência tal que, para cada um , é um vetor de entradas não negativas que determinam os custos de processamento para os estados ao processar a tarefa. ${\ 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}$

Um algoritmo para o sistema de tarefas produz uma programação que determina a seqüência de estados. Por exemplo, significa que a tarefa é executada no estado . O custo de processamento de uma programação é ${\ 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)).}$

O objetivo do algoritmo é encontrar um cronograma de forma que o custo seja minimizado.

Resultados Conhecidos

Como de costume para problemas online, a medida mais comum para analisar algoritmos para sistemas de tarefas métricas é a análise competitiva , onde o desempenho de um algoritmo online é comparado ao desempenho de um algoritmo offline ótimo. Para algoritmos online determinísticos, há um limite estreito na razão competitiva devido a Borodin et al. (1992). ${\ displaystyle 2n-1}$

Para algoritmos online randomizados, a razão competitiva é limitada por inferior e superior por . O limite inferior é devido a Bartal et al. (2006,2005). O limite superior deve-se a Bubeck, Cohen, Lee e Lee (2018) que melhoraram um resultado de Fiat e Mendel (2003). ${\ displaystyle \ Omega (\ log n / \ log \ log n)}$${\ displaystyle O \ left ((\ log n) ^ {2} \ right)}$

Existem muitos resultados para vários tipos de métricas restritas.

Veja também

• Modelo adversário
• Analise competitiva
• Problema de servidor K
• Algoritmo online
• Algoritmo de substituição de página
• Computação em tempo real

Referências

• Yair Bartal; Avrim Blum; Carl Burch e Andrew Tomkins (1997). "Um algoritmo polylog (n) -Competitive para sistemas de tarefas métricas". Anais do Vigésimo Nono Simpósio Anual da ACM na Teoria da Computação . pp. 711–719. doi : 10.1145 / 258533.258667 .

• Yair Bartal, Béla Bollobás , Manor Mendel (2006). "Teoremas do tipo Ramsey para espaços métricos com aplicações a problemas online". Journal of Computer and System Sciences . 72 (5): 890–921. arXiv : cs / 0406028 . doi : 10.1016 / j.jcss.2005.05.008 . CS1 maint: vários nomes: lista de autores ( link )

• Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor (2005). "Em fenômenos métricos do tipo Ramsey". Annals of Mathematics . 162 (2): 643–709. arXiv : math / 0406353 . doi : 10.4007 / annals.2005.162.643 . CS1 maint: vários nomes: lista de autores ( link )

• Allan Borodin e Ran El-Yaniv (1998). Computação Online e Análise Competitiva . Cambridge University Press. pp. 123–149.
• Allan Borodin , Nati Linial e Michael Saks (1992). "Um algoritmo online ideal para sistemas de tarefas métricas". Jornal do ACM . 39 (4): 745–763. doi : 10.1145 / 146585.146588 . CS1 maint: vários nomes: lista de autores ( link )

• Amos Fiat & Manor Mendel (2003). "Melhores Algoritmos para Sistemas e Aplicações de Tarefas 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 e Yin Tat Lee (2019). "Sistemas de tarefas métricas em árvores via descida de espelho e colagem injusta". Procedimentos do trigésimo Simpósio Anual ACM-SIAM sobre Algoritmos Discretos . arXiv : 1807.04404 .