Metrical task system

Metrical task systems (MTS) are abstract models for competitive analysis of online computation. Metrical task systems play roles in online problems such as paging, list accessing, and the k-server problem (in finite spaces). Metrical task systems were formulated by Borodin, Linial, and Saks.

General Description

In gernal terms, a metrical task system consists of a metric space with a metric and a transition table. These are used to represent all possible configurations.

See Also

• Adversary Model
• Competitive analysis
• List accessing problem
• Online algorithm
• Paging Problem
• Real-time computing
• K-server problem

References

• Allan Borodin and Ran El-Yaniv (1998). Online Computation and Competitive Analysis. Cambridge University Press. pp. 123–149. {{cite book}}: External link in |title= (help)
• A. Borodin, N. Linial, and M. Saks. An optimal online algorithm for metrical task systems. Journal of the ACM, 39:745-763,1992.