Known Results
As usual for online problems, the most common measure to analyze algorithms for metrical task systems is the competitive analysis, where the performance of an online algorithm is compared to the performance of an optimal offline algorithm. For deterministic online algorithms, there is a tight bound on the competitive ratio due to Borodin et al. (1992).
For randomized online algorithms, the competitive ratio is lower bounded by and upper bounded by . The lower bound is due to Bartal et al. (2006,2005). The upper bound is due to Fiat and Mendel (2003) who improved upon a result of Bartal et al. (1997).
There are many results for various types of restricted metrics.
Read more about this topic: Metrical Task System
Famous quotes containing the word results:
“Intellectual despair results in neither weakness nor dreams, but in violence.... It is only a matter of knowing how to give vent to one’s rage; whether one only wants to wander like madmen around prisons, or whether one wants to overturn them.”
—Georges Bataille (1897–1962)
“Being a parent is unlike any previous job—the results of any one action are not clearly visible for a long time, if at all.”
—Anonymous Mother. As quoted in Between Generations by Ellen Galinsky, ch. 2 (1981)