Improved approximation algorithms for broadcast scheduling

N. Bansal, D. Coppersmith, M. Sviridenko

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

    21 Citations (Scopus)

    Abstract

    We consider two scheduling problems in the broadcast setting. The first is that of minimizing the average response time of requests. For the offline version of this problem we give an algorithm with an approximation ratio of O(log2 (n)/ log log(n)), where n is the total number of pages. This substantially improves the previously best known approximation factor of O(vn) for the problem [3]. Our second result is for the profit maximization version of the broadcast scheduling problem. Here each request has a deadline and a profit which is obtained if the request is satisfied before its deadline. The goal is to maximize the total profit. We give an algorithm with an approximation ratio of 5/6, which improves the previously best known approximation guarantee of 3/4 for the problem [13].
    Original languageEnglish
    Title of host publicationProceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'06, Miami FL, USA, January 22-24, 2006)
    Place of PublicationNew York
    PublisherAssociation for Computing Machinery, Inc
    Pages344-353
    ISBN (Print)0-89871-605-5
    Publication statusPublished - 2006

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

    Cite this