An optimal on-line algorithm for metrical task system

ABSTRACT

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

REFERENCES

• 1: S. Ben-David , A. Borodin , R. Karp , G. Tardos , A. Wigderson, On the power of randomization in online algorithms, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.379-386, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100268]
• 2: 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]
• 3: James Richard Bitner, Heuristics that dynamically alter data structures to reduce their access time., 1976
• 4: BITNER, J. R. Heuristics that dynamically organize data structures. SIAM J. Comput. 8 (1979), 82-110.
• 5: M. Chrobak , H. Karloff , T. Payne , S. Vishwanathan, New results on server problems, SIAM Journal on Discrete Mathematics, v.4 n.2, p.172-181, May 1991 [doi>10.1137/0404017]
• 6: Marek Chrobak , Lawrence L. Larmore, An optimal on-line algorithm for K-servers on trees, SIAM Journal on Computing, v.20 n.1, p.144-148, Feb. 1991 [doi>10.1137/0220008]
• 7: CHUNO, F. R. K., GRAHAM, R. L., AND SAXS, M. A dynamic location problem for graphs. Combbtatorica 9 (1989), 111-131.
• 8: D. Coppersmith , P. Doyle , P. Raghavan , M. Snir, Random walks on weighted graphs, and applications to on-line algorithms, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.369-378, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100266]
• 9: Amos Fiat , Richard M. Karp , Michael Luby , Lyle A. McGeoch , Daniel D. Sleator , Neal E. Young, Competitive paging algorithms, Journal of Algorithms, v.12 n.4, p.685-699, Dec. 1991 [doi>10.1016/0196-6774(91)90041-V]
• 10: FIAT, A., RABANI, Y., AND RAVlD, Y. Competitive k-Server Algorithms. In Proceedings of the 31st Annual Symposium on Foundations of Computer Science. IEEE, New York, 1990, pp. 454-463.
• 11: GONNET, G., MUNRO, J. I., AND SUWANDA, H. Exegesis of self-organizing linear search. SIAM J. Comput. 10, 3 (1981), 613-637.
• 12: E. F. Grove, The harmonic online K-server algorithm is competitive, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.260-266, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103448]
• 13: HEYMAN, D., AND SOBEL, M. Stochastic Models in Operations Research. vol. II. McGraw-Hill, New York, 1984.
• 14: KAN, Y. C., AND ROSS, S.M. Optimal list order under partial memory constraints. J. Appl. Prob. 17 (1980), 1004-1015.
• 15: KARLIN, A. R., MANASSE, M. S., RUDOLPH, L., AND SLEATOR, D. D. Competitive snoopy caching. Algorithmica 3, 1 (1988), 79-119.
• 16: Mark S. Manasse , Lyle A. McGeoch , Daniel D. Sleator, Competitive algorithms for server problems, Journal of Algorithms, v.11 n.2, p.208-230, Jun. 1990 [doi>10.1016/0196-6774(90)90003-W]
• 17: McGEOCH, L. A., AND SLEATOR, D.D. A strongly competitive randomized paging algorithm. Algorithmica, to appear.
• 18: Prabhakar Raghavan , Marc Snir, Memory Versus Randomization in On-line Algorithms (Extended Abstract), Proceedings of the 16th International Colloquium on Automata, Languages and Programming, p.687-703, July 11-15, 1989
• 19: 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]
• 20: Ross, S. Applied Probability Models with Optimization Applications. Holden-Day, Calif. 1970.
• 21: 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]
• 22: TARJAN, R. E. Amortized computational complexity. SIAM J. Alg. Disc. Math. 6 (1985), 306-318.
• 23: YAO, A. Probabilistic computations: Towards a unified measure of complexity. In Proceedings of the 18th Annual Symposium on Foundations of Computer Science. IEEE, New York, 1977, pp. 222-227.

INDEX TERMS

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

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

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

General Terms:
Algorithms, Performance, Theory

Keywords:
competitive analysis, on-line algorithms