Improved approximation algorithms for broadcast scheduling

N. Bansal, D. Coppersmith, M. Sviridenko

    Research output: Contribution to journalArticleAcademicpeer-review

    13 Citations (Scopus)
    95 Downloads (Pure)

    Abstract

    We consider scheduling policies in a client-server system where the server delivers data by broadcasting it to the users. In thesimplest model of the problem, there is a single server that holds $n$ pages of unit size. Multiple requests for these pages arrive over time. At each time slot the server broadcasts exactly one page which satisfies all of the outstanding requests for this page at that time. We consider the problem of minimizing the average response time of requests, where the response time of the request is the duration since the request is placed until the time it is satisfied. For the offline version of this problem we give an algorithm with an approximation ratio of $O(\log^2(n) / \log \log(n))$. More generally, for any $\epsilon>0$, the algorithm achieves an average response time of $(2+\epsilon) \cdot \text{OPT} + O(\log n \cdot \log_{(1+\epsilon)} n)$, which is useful when the optimum value is large. This substantially improves the previously best known approximation factor of $O(\sqrt{n})$ for the problem [N. Bansal, M. Charikar, S. Khanna, and J. Naor, Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Vancouver, British Columbia, ACM, New York, SIAM, Philadelphia, 2005, pp. 215–221]. Our result is based on iteratively relaxing and rounding an auxiliary linear program derived from a natural linear programming relaxation of the problem.
    Original languageEnglish
    Pages (from-to)1157-1174
    JournalSIAM Journal on Computing
    Volume38
    Issue number3
    DOIs
    Publication statusPublished - 2008

    Fingerprint Dive into the research topics of 'Improved approximation algorithms for broadcast scheduling'. Together they form a unique fingerprint.

  • Cite this