An optimal deterministic algorithm for online b-matching

We consider the natural online version of the well-known unweighted b-match ing problem. We present a deterministic algorithm BALANCE whose competitive ratio is 1-1/(1+1/b)(a), where a is the number of online servers per site, and b is the number of adversarial servers per site. We show that the comp etitive ratio of every deterministic online algorithm is at least 1 - 1/(1 + 1/b)(a). Hence, BALANCE is optimally competitive, including low-order ter ms. In the case a = b, the competitive ratio of BALANCE approaches 1 - 1/e approximate to 0.63 as b grows. (C) 2000 Elsevier Science B.V. All rights r eserved.