On-line load balancing of temporary tasks revisited

Abstract. We study load balancing problems of temporary jobs (i.e., jobs that arrive and depart at unpredictable time) in two dierent contexts, namely, machines and network paths. Such problems are known as machine load balancing and virtual circuit routing in the literature. We present new on-line algorithms and improved lower bounds.