Metrical task system

A task system is a pair (S,d) where S=\{s_1,s_2,\dotsc,s_n\} is a set of states and d:S \times S \rightarrow \mathbb{R} is a distance function. If d is a metric, (S,d) is a metrical task system. An input to the task system is a sequence \sigma = T_1,T_2,\dotsc,T_l such that for each i, T_i is a vector of n non-negative entries that determine the processing costs for the n states when processing the ith task. An algorithm for the task system produces a schedule \pi that determines the sequence of states. For instance, \pi(i)=s_j means that the ith task T_i is run in state s_j. The processing cost of a schedule is \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. ==Known results==

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 2n-1 on the competitive ratio due to Borodin et al. (1992). For randomized online algorithms, the competitive ratio is lower bounded by \Omega(\log n / \log\log n) and upper bounded by 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. ==See also==