An optimal online algorithm for metrical task systems

ABSTRACT

In practice, almost all dynamic systems require decisions to be made online, without full knowledge of their future impact on the system. We introduce a general model for the processing of sequences of tasks and develop a general online decision algorithm. We show that, for an important class of special cases, this algorithm is optimal among all online 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 O.) 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 state transition costs incurred. An online scheduling algorithm is one that chooses si only knowing T1 T2 … Ti. Such an algorithm operates within waste factor w if, on any input task sequence, its costs is within an additive constant of w times the optimal offline schedule cost. The online waste factor w(S, d) is the infirm waste factor of any online scheduling algorithm for (S, d). We show that w(S, d) = 2|S| - 1 for every task system in which d symmetric, and w(S, d) = &Ogr;(|S|2) for every task system.

REFERENCES

• BM: Jon L. Bentley , Catherine C. McGeoch, Amortized analyses of self-organizing sequential search heuristics, Communications of the ACM, v.28 n.4, p.404-411, April 1985 [doi>10.1145/3341.3349]
• Bi1: James Richard Bitner, Heuristics that dynamically alter data structures to reduce their access time., 1976
• Bi2: J. R. Bitner, "Heuristics that dynamically organize data structures", SIAM J. Comp. 8 (1979), 82-110.
• CGS: F.R.K. Chung, R. L. Graham and M. Saks, "A Dynamic Location Problem for graphs", p, reprint.
• CHS: F R Chung , D J Hajela , P D Seymour, Self-organizing sequential search and Hilbert's inequalities, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.217-223, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22170]
• GMS: G. Gonnet, J. I. Munro and H. Suwanda, "Toward self-organizing sequential search heuristics", Proc. 20th IEEE Symp. Foundations Computer-Science, (1979), 169-174.
• HS: D. Heyman and M. Sol)el, "Stochastic Models in Operations Research", Volume lI, McGraw-Hill, (1984).
• KR: Y.C. Kan and S. M. Ross, "Optimal list order under partial memory constraints", J. Appl. Prob. 17 (1980), 1004-1015.
• KMRS: A. R. Karlin, M. S. Manasse, L. Rudolph and D. D. Sleator, "Competitive Snoopy Caching", Proc. 27th IEEE Syrup. Foundations of Computer Science (1986), 244-254.
• R: Ronald Rivest, On self-organizing sequential search heuristics, Communications of the ACM, v.19 n.2, p.63-67, Feb. 1976 [doi>10.1145/359997.360000]
• ST: Daniel D. Sleator , Robert E. Tarjan, Amortized efficiency of list update and paging rules, Communications of the ACM, v.28 n.2, p.202-208, Feb. 1985 [doi>10.1145/2786.2793]
• T: R. E. Tarjan, "Amortized computational complexity" SIAM J Ai~. Disc. Math., 6(1985), 306-318.

INDEX TERMS

Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching; Sequencing and scheduling

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Measurement, Theory, Verification