Better Algorithms and Hardness for Broadcast Scheduling via a Discrepancy Approach

Abstract

We study the broadcast scheduling problem with the objective of minimizing the average response time. There is a single server that can hold n pages of unit size, and multiple requests for these pages arrive over time. At each time slot the server can broadcast one page which satisfies all the outstanding requests for this page at that time. The goal is to find a schedule to minimize the average response time of the requests, i.e. the duration since a request arrives until it is satisfied.

We give an Õ(log1,5 n) approximation algorithm for the problem improving upon the previous Õ(log 2 n) approximation. We also show an Ω(log1/2–∊n) hardness result, and an integrality gap of Ω(log n) for the natural LP relaxation for the problem. Prior to our work, only NP-Hardness and a (tiny) constant integrality gap was known. These results are based on establishing a close connection to the discrepancy minimization problem for permutation set-systems. Specifically, our improved approximation is based on using recent algorithmic ideas developed for discrepancy minimization. Our integrality gap is obtained from the Ω(log n)-lower bound on the discrepancy of 3-permutations, while our hardness result is based on establishing the first hardness result for the discrepancy of ℓ-permutations.