The competitiveness of on-line assignments

ABSTRACT

Consider the on-line problem where a number of servers are ready to provide service to a set of customers. Each customer's job can be handled by any of a subset of the servers. Customers arrive one-by-one and the problem is to assign each customer to an appropriate server in a manner that will balance the load on the servers. This problem can be modeled in a natural way by a bipartite graph where the vertices of one side (customers) appear one at a time and the vertices of the other side (servers) are known in advance. We derive tight bounds on the competitive ratio in both deterministic and randomized cases. Let n denote the number of servers. In the deterministic case we provide an on-line algorithm that achieves a competitive ratio of k = [log2 n] (up to an additive 1) and prove that this is the best competitive ratio that can be achieved by any deterministic on-line algorithm. In a similar way we prove that the competitive ratio for the randomized case is k=ln(n) (up to an additive 1). We conclude that for this problem, randomized algorithms differ from deterministic ones by precisely a constant factor.

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: A. Fiat, R. Karp, M. Luby, L. McGeoch, D. Sleator, and N. Young, Competitive paging algorithms, Tech. Rep. CMU-CS-88-196, School of computer science Carnegie-Mellon University, 1988.
• 3: S. Irani, Coloring inductive graphs on-line, in Proceedings of the 31st Annual Symposium on Foundations of Computer Science, St. Louis, Missouri, October 1990, pp. 470-479.
• 4: R. M. Karp , U. V. Vazirani , V. V. Vazirani, An optimal algorithm for on-line bipartite matching, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.352-358, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100262]
• 5: L. Lovsz , M. Saks , W. T. Trotter, An on-line graph coloring algorithm with sublinear performance ratio, Discrete Mathematics, v.75 n.1-3, p.319-325, 1989 [doi>10.1016/0012-365X(89)90096-4 ]
• 6: Mark Manasse , Lyle McGeoch , Daniel Sleator, Competitive algorithms for on-line problems, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.322-333, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62243]
• 7: 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]
• 8: S. Vishwastathan, Randomized on-line graph coloring, in Proceedings of the 31st Annum Symposium on Foundations of Computer Science, St. Louis, Missouri, October 1990, pp. 464-469.

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.1 COMPUTATION BY ABSTRACT DEVICES

General Terms:
Algorithms, Theory, Verification