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 variaty 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 assignes 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).
Read more about Metrical Task System: Formal Definition, Known Results
Other articles related to "metrical task system, metrical task systems":
... the most common measure to analyze algorithms for metrical task systems is the competitive analysis, where the performance of an online algorithm is ...
Famous quotes containing the words system and/or task:
“A person, seasoned with a just sense of the imperfections of natural reason, will fly to revealed truth with the greatest avidity: while the haughty Dogmatist, persuaded that he can erect a compleat system of Theology by the mere help of philosophy, disdains any further aid, and rejects this adventitious instructor.”
—David Hume (1711–1776)
“In a period of a people’s life that bears the designation “transitional,” the task of a thinking individual, of a sincere citizen of his country, is to go forward, despite the dirt and difficulty of the path, to go forward without losing from view even for a moment those fundamental ideals on which the entire existence of the society to which he belongs is built.”
—Ivan Sergeevich Turgenev (1818–1883)