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.
Publication
SODA 2005
Conference paper
Approximating the average response time in broadcast scheduling
Abstract
We consider the problem of approximating the minimum average response time in on-demand data broadcasting systems. The best approximation factors known for this problem involve resource augmentation. We provide the first non-trivial approximation factors in the absence of resource augmentation, achieving an additive O(√n)-approximation, where n is the number of distinct pages. Our result can be extended, for any ε > 0, to a (1 + ε)-speed, additive O(1/ε)-approximation algorithm. Prior to our work, no non-trivial approximation factor was known for the case of ε < 1.