Metrical task systems

From Wikipedia, the free encyclopedia

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.

[edit] General Description

In general 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.

[edit] See also

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

[edit] References

• Allan Borodin and Ran El-Yaniv (1998). Online Computation and Competitive Analysis. Cambridge University Press, 123-149. 
• A. Borodin, N. Linial, and M. Saks. An optimal online algorithm for metrical task systems. Journal of the ACM, 39:745-763,1992.