About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Abstract
This papei examines the problem of balancing the job load in a network of processors, and introduces an online algorithm for scheduling a sequence of jobs in a competitive manner. The algorithm is shown to be polylog(n)-competitive according to a strict definition that forces the online algorithm to be competitive even when considering any bounded area of the network and bounded period of time. We also analyze the common greedy feedback-based approach, and provide matching lower and upper bounds (up to a polylogarithmic factor) for the tradeoff between the costs of searches and updates under this approach.