Metrical task systems

Metrical task systems

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

ee also

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

References

* cite book | author= Allan Borodin and Ran El-Yaniv | title= [http://www.cs.technion.ac.il/~rani/book.html "Online Computation and Competitive Analysis"]
publisher= Cambridge University Press
date= 1998 | pages= 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.


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • 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 …   Wikipedia

  • Nati Linial — Nathan (Nati) Linial (born 1953 in Haifa, Israel)[1] is an Israeli mathematician and computer scientist, a professor in the Rachel and Selim Benin School of Computer Science and Engineering at the Hebrew University of Jerusalem,[2] and an ISI… …   Wikipedia

  • Online algorithm — In computer science, an online algorithm is one that can process its input piece by piece in a serial fashion, i.e., in the order that the input is fed to the algorithm, without having the entire input available from the start. In contrast, an… …   Wikipedia

  • K-server problem — The k server problem is a problem of theoretical computer science in the category of online algorithms, one of two abstract problems on metric spaces that are central to the theory of competitive analysis (the other being metrical task systems).… …   Wikipedia

  • Online algorithm — En informatique, un algorithme online (algorithme en ligne) est un algorithme qui reçoit son entrée (son input) prédécoupée en petits morceaux, et qui commence à calculer dès le premier petit morceau reçu, puis continue à traiter, en série, les… …   Wikipédia en Français

  • Islamic arts — Visual, literary, and performing arts of the populations that adopted Islam from the 7th century. Islamic visual arts are decorative, colourful, and, in religious art, nonrepresentational; the characteristic Islamic decoration is the arabesque.… …   Universalium

  • MUSIC — This article is arranged according to the following outline: introduction written sources of direct and circumstantial evidence the material relics and iconography notated sources oral tradition archives and important collections of jewish music… …   Encyclopedia of Judaism

  • English literature — Introduction       the body of written works produced in the English language by inhabitants of the British Isles (including Ireland) from the 7th century to the present day. The major literatures written in English outside the British Isles are… …   Universalium

  • French literature — Introduction       the body of written works in the French language produced within the geographic and political boundaries of France. The French language was one of the five major Romance languages to develop from Vulgar Latin as a result of the …   Universalium

  • BIBLE — THE CANON, TEXT, AND EDITIONS canon general titles the canon the significance of the canon the process of canonization contents and titles of the books the tripartite canon …   Encyclopedia of Judaism

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”