Metrical task system

A task system is a pair ${\displaystyle (S,d)}$ where ${\displaystyle S=\{s_{1},s_{2},\dotsc ,s_{n}\}}$ is a set of states and ${\displaystyle d:S\times S\rightarrow \mathbb {R} }$ is a distance function. If ${\displaystyle d}$ is a metric, ${\displaystyle (S,d)}$ is a metrical task system. An input to the task system is a sequence ${\displaystyle \sigma =T_{1},T_{2},\dotsc ,T_{l}}$ such that for each ${\displaystyle i}$, ${\displaystyle T_{i}}$ is a vector of ${\displaystyle n}$ non-negative entries that determine the processing costs for the ${\displaystyle n}$ states when processing the ${\displaystyle i}$th task.

An algorithm for the task system produces a schedule ${\displaystyle \pi }$ that determines the sequence of states. For instance, ${\displaystyle \pi (i)=s_{j}}$ means that the ${\displaystyle i}$th task ${\displaystyle T_{i}}$ is run in state ${\displaystyle s_{j}}$. The processing cost of a schedule is ${\displaystyle \mathrm {cost} (\pi ,\sigma )=\sum _{i=1}^{l}d(\pi (i-1),\pi (i))+T_{i}(\pi (i)).}$

The objective of the algorithm is to find a schedule such that the cost is minimized.

As usual for online problems, the most common measure to analyze algorithms for metrical task systems is the competitive analysis, where the performance of an online algorithm is compared to the performance of an optimal offline algorithm. For deterministic online algorithms, there is a tight bound ${\displaystyle 2n-1}$ on the competitive ratio due to Borodin et al. (1992).

For randomized online algorithms, the competitive ratio is lower bounded by ${\displaystyle \Omega (\log n/\log \log n)}$ and upper bounded by ${\displaystyle O\left((\log n)^{2}\right)}$. The lower bound is due to Bartal et al. (2006,2005). The upper bound is due to Bubeck, Cohen, Lee and Lee (2018) who improved upon a result of Fiat and Mendel (2003).

There are many results for various types of restricted metrics.

• Adversary model
• Competitive analysis
• K-server problem
• Online algorithm
• Page replacement algorithm
• Real-time computing

• Yair Bartal; Avrim Blum; Carl Burch & Andrew Tomkins (1997). "A polylog(n)-Competitive Algorithm for Metrical Task Systems". Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing. pp. 711–719. doi:10.1145/258533.258667.

• Yair Bartal, Béla Bollobás, Manor Mendel (2006). "Ramsey-type theorems for metric spaces with applications to online problems". Journal of Computer and System Sciences. 72 (5): 890–921. arXiv:cs/0406028. doi:10.1016/j.jcss.2005.05.008.CS1 maint: multiple names: authors list (link)

• Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor (2005). "On metric Ramsey-type phenomena". Annals of Mathematics. 162 (2): 643–709. arXiv:math/0406353. doi:10.4007/annals.2005.162.643.CS1 maint: multiple names: authors list (link)

• Allan Borodin and Ran El-Yaniv (1998). Online Computation and Competitive Analysis. Cambridge University Press. pp. 123–149.
• Allan Borodin, Nati Linial, and Michael Saks (1992). "An optimal online algorithm for metrical task systems". Journal of the ACM. 39 (4): 745–763. doi:10.1145/146585.146588.CS1 maint: multiple names: authors list (link)

• Amos Fiat & Manor Mendel (2003). "Better Algorithms for Unfair Metrical Task Systems and Applications". SIAM J. Comput. 32 (6): 1403–1422. arXiv:cs/0406034. doi:10.1137/S0097539700376159.

• Sébastien Bubeck; Michael B. Cohen; James R. Lee & Yin Tat Lee (2019). "Metrical task systems on trees via mirror descent and unfair gluing". Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms. arXiv:1807.04404.