THE COMPETITIVENESS OF ONLINE ASSIGNMENTS

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 = [log(2) 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. (C) 1995 Academic Press, Inc.