Academic
Publications
An optimal on-line algorithm for metrical task system

An optimal on-line algorithm for metrical task system,10.1145/146585.146588,Journal of The ACM,Allan Borodin,Nathan Linial,Michael E. Saks

An optimal on-line algorithm for metrical task system   (Citations: 116)
BibTex | RIS | RefWorks Download
In practice, almost all dynamic systems require decisions to be made on-line, without full knowledge of their future impact on the system. A general model for the processing of sequences of tasks is introduced, and a general on-line decision algorithm is developed. It is shown that, for an important class of special cases, this algorithm is optimal among all on-line algorithms.Specifically, a task system (S,d) for processing sequences of tasks consists of a set S of states and a cost matrix d where d(i, j is the cost of changing from state i to state j (we assume that d satisfies the triangle inequality and all diagonal entries are 0). The cost of processing a given task depends on the state of the system. A schedule for a sequence T1, T2,…, Tk of tasks is a sequence s1, s2,…,sk of states where si is the state in which Ti is processed; the cost of a schedule is the sum of all task processing costs and the state transition costs incurred.An on-line scheduling algorithm is one that chooses si only knowing T1T2…Ti. Such an algorithm is w-competitive if, on any input task sequence, its cost is within an additive constant of w times the optimal offline schedule cost. The competitive ratio w(S, d) is the infimum w for which there is a w-competitive on-line scheduling algorithm for (S,d). It is shown that w(S, d) = 2|S|–1 for every task system in which d is symmetric, and w(S, d) = O(|S|2) for every task system. Finally, randomized on-line scheduling algorithms are introduced. It is shown that for the uniform task system (in which d(i,j) = 1 for all i,j), the expected competitive ratio w¯(S,d) = O(log|S|).
Journal: Journal of The ACM - JACM , vol. 39, no. 4, pp. 745-763, 1992
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...Further, for “metrical task systems” [33]–[35], which generalize rent-or-buy problems and the data center optimization problem, there are many algorithms available, but they typically have competitive ratios that are poly-logarithmic in the number of servers...

    Minghong Linet al. Dynamic right-sizing for power-proportional data centers

    • ...We build upon two well-studied online problems, weighted paging/caching [1,21] and Metrical Task System (MTS) [4,8] (see our technical report [9] for details), and extend them to address two new challenges specific to our problem: (1) optimizing energy costs of executing batch jobs under time-varying electricity prices and job demand, and (2) balancing energy savings with bandwidth costs to minimize the total operation cost...
    • ...Since our problem is a generalization of the MTS problem [8], we get a lower bound of Ω(log n) on the competitiveness of any online algorithm where n is the number of datacenters...

    Niv Buchbinderet al. Online Job-Migration for Reducing the Electricity Bill in the Cloud

    • ...A metrical task system [26], [27] (MTS) is defined to be a pair (X;R) such that 1) X is a metric space...
    • ...The Work Function Algorithm: For any metrical task system, (X;R), the work function algorithm [26], [27], [28] is defined as follows...

    Eddy Caronet al. On-Line Optimization of Publish/Subscribe Overlays

    • ...1.1 Problem Definitions and Preliminaries Metrical Task System (MTS) and Unfair MTS: The MTS problem was introduced by Borodin et al. [6] as a generalization of various online problems...
    • ...Borodin et al. [6] gave a tight deterministic 2n 1 competitive algorithm for any metric, and a (log n)-competitive randomized algorithm for the uniform metric...

    Nikhil Bansalet al. Towards the Randomized k-Server Conjecture: A Primal-Dual Approach

    • ...This is a concrete example of the metrical task system (MTS) problem, first introduced by Borodin, Linial and Saks [1]...
    • ...Prior Work. Borodin, Linial and Saks [1] showed that the lower bound on the competitive ratio of any deterministic algorithm over any metric is 2n −1. They also designed an algorithm, the Work-Function algorithm, that achieves exactly this bound...
    • ...For the uniform case, Bartal, Linial and Saks [1] showed a lower bound on the competitive ratio for any algorithm of Hn ,t henth harmonic number...
    • ...They [1] also designed an algorithm, Marking, that has competitive ratio2Hn...
    • ...This paper focuses entirely on the construction of work-based algorithms, where the algorithm can forget about the sequence of cost vectors c 1 ,..., c t and simply use W t to choose p t . This algorithmic restriction has been used as early as [1] and appears...
    • ...Here, the algorithm must choose a probability distributions p t ∈ Δn on each round t, and an adversary then chooses a loss vector l t ∈ [0,1] n .L etL t = � t=1 l s . Then the algorithm’s goal is to minimize...

    Jacob Abernethyet al. A Regularization Approach to Metrical Task Systems

Sort by: