ONLINE LOAD BALANCING AND NETWORK FLOW

In this paper we study two problems that can be viewed as on-line game s on a dynamic bipartite graph. The first problem is on-line load bala ncing with preemption. A centralized scheduler must assign tasks to se rvers, processing on-line a sequence of task arrivals and departures. Each task is restricted to run on some subset of the servers. The sche duler attempts to keep the load well-balanced. If preemptive reassignm ents are disallowed. Azar et al. [3] proved a lower bound of Omega(roo t n) on the ratio between the maximum load achieved by an on-line algo rithm and the optimum off-line maximum load. We show that this ratio c an be greatly reduced by an efficient scheduler using only a small amo unt of rescheduling. We then apply these ideas to network flow. Cheriy an and Hagerup [6] introduced an on-line game on a bipartite graph as a fundamental step in improving algorithms for computing the maximum f low in networks. They described a randomized strategy to play the game . King et al. [11] studied a modified version of this game, called ''n ode kill,'' and gave a deterministic strategy. We obtain an improved d eterministic algorithm for the node kill game land hence for maximum f low) in all but the sparsest graphs. The running time achieved is O (m n log(m/n) n + n(2) log(2+epsilon) n), compared with King et al.'s O ( mn + n(2+epsilon)). These problems combine a demand for good competiti ve ratios with more traditional requirements of implementation efficie ncy. Our solutions deal with the tradeoffs between these measures.