Metrical task system

Task systems are mathematical objects used to model the set of possible configuration of online algorithms. They were introduced by Borodin, Linial and Saks (1992) to model a variety of online problems. A task system determines a set of states and costs to change states. Task systems obtain as input a sequence of requests such that each request assigns processing times to the states. The objective of an online algorithm for task systems is to create a schedule that minimizes the overall cost incurred due to processing the tasks with respect to the states and due to the cost to change states. Task systems are mathematical objects used to model the set of possible configuration of online algorithms. They were introduced by Borodin, Linial and Saks (1992) to model a variety of online problems. A task system determines a set of states and costs to change states. Task systems obtain as input a sequence of requests such that each request assigns processing times to the states. The objective of an online algorithm for task systems is to create a schedule that minimizes the overall cost incurred due to processing the tasks with respect to the states and due to the cost to change states. If the cost function to change states is a metric, the task system is a metrical task system (MTS). This is the most common type of task systems.Metrical task systems generalize online problems such as paging, list accessing, and the k-server problem (in finite spaces). A task system is a pair ( S , d ) {displaystyle (S,d)} where S = { s 1 , s 2 , … , s n } {displaystyle S={s_{1},s_{2},dotsc ,s_{n}}} is a set of states and d : S × S → R {displaystyle d:S imes S ightarrow mathbb {R} } is a distance function. If d {displaystyle d} is a metric, ( S , d ) {displaystyle (S,d)} is a metrical task system. An input to the task system is a sequence σ = T 1 , T 2 , … , T l {displaystyle sigma =T_{1},T_{2},dotsc ,T_{l}} such that for each i {displaystyle i} , T i {displaystyle T_{i}} is a vector of n {displaystyle n} non-negative entries that determine the processing costs for the n {displaystyle n} states when processing the i {displaystyle i} th task. An algorithm for the task system produces a schedule π {displaystyle pi } that determines the sequence of states. For instance, π ( i ) = s j {displaystyle pi (i)=s_{j}} means that the i {displaystyle i} th task T i {displaystyle T_{i}} is run in state s j {displaystyle s_{j}} . The processing cost of a schedule is c o s t ( π , σ ) = ∑ i = 1 l d ( π ( i − 1 ) , π ( i ) ) + T i ( π ( i ) ) . {displaystyle mathrm {cost} (pi ,sigma )=sum _{i=1}^{l}d(pi (i-1),pi (i))+T_{i}(pi (i)).}