Elsevier

Journal of Algorithms

Volume 18, Issue 2, March 1995, Pages 221-237
Journal of Algorithms

Regular Article
The Competitiveness of On-Line Assignments

https://doi.org/10.1006/jagm.1995.1008Get rights and content

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 = [log2n] (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 (0)

Cited by (143)

  • Rejecting jobs to minimize load and maximum flow-time

    2018, Journal of Computer and System Sciences
  • Multiprofessor scheduling

    2018, Discrete Applied Mathematics
  • A General Framework for Learning-Augmented Online Allocation

    2023, Leibniz International Proceedings in Informatics, LIPIcs
View all citing articles on Scopus
View full text