THE COMPETITIVENESS OF ONLINE ASSIGNMENTS

Consider the on-line problem, where a number of servers are ready to p rovide service to a set of customers. Each customer's job can be handl ed 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 m anner that will balance the load on the servers. This problem can be m odeled 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 s ide (servers) are known in advance. We derive tight bounds on the comp etitive ratio in both deterministic and randomized cases. Let n denote the number of servers. In the deterministic case we provide an on-lin e 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, rand omized algorithms differ from deterministic ones by precisely a consta nt factor. (C) 1995 Academic Press, Inc.