Approximating the average response time in broadcast scheduling

N. Bansal, M. Charikar, S. Khanna, J. Naor

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    27 Citations (Scopus)

    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(vn)-approximation, where n is the number of distinct pages. Our result can be extended, for any e > 0, to a (1 + e)-speed, additive O(1/e)-approximation algorithm. Prior to our work, no non-trivial approximation factor was known for the case of e <1.
    Original languageEnglish
    Title of host publicationProceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'05, Vancouver BC, Canada, January 23-25, 2005)
    Place of PublicationNew York
    PublisherAssociation for Computing Machinery, Inc
    Pages215-221
    ISBN (Print)0-89871-585-7
    Publication statusPublished - 2005

    Fingerprint Dive into the research topics of 'Approximating the average response time in broadcast scheduling'. Together they form a unique fingerprint.

    Cite this