Algorithms for minimizing response time in broadcast scheduling

Rajiv Gandhi, Samir Khuller, Yoo Ah Kim, Yung Chun Wan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

18 Scopus citations


In this paper we study the following problem. There are n pages which clients can request at any time. The arrival times of requests for pages are known. Several requests for the same page may arrive at different times. There is a server that needs to compute a good broadcast schedule. Outputting a page satisfies all outstanding requests for the page. The goal is to minimize the average waiting time of a client. This problem has recently been shown to be NP-hard. For any fixed α, 0 < α ≤ 1/2, we give a 1/α- speed, polynomial time algorithm with an approximation ratio of 1/1-α. For example, setting α = 1/2 gives a 2-speed, 2-approximation algorithm. In addition, we give a 4-speed, 1-approximation algorithm improving the previous bound of 6-speed, 1-approximation algorithm.

Original languageEnglish (US)
Title of host publicationInteger Programming and Combinatorial Optimization - 9th International IPCO 2002 Conference, Proceedings
EditorsWilliam J. Cook, Andreas S. Schulz
PublisherSpringer Verlag
Number of pages14
ISBN (Print)9783540478676
StatePublished - 2002
Externally publishedYes
Event9th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2002 - Cambridge, MA, United States
Duration: May 27 2002May 29 2002

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2337 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other9th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2002
Country/TerritoryUnited States
CityCambridge, MA

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Algorithms for minimizing response time in broadcast scheduling'. Together they form a unique fingerprint.

Cite this