Algorithms for minimizing response time in broadcast scheduling

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

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

22 Scopus citations

Abstract

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 in advance. 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 < α \le 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)
Pages (from-to)597-608
Number of pages12
JournalAlgorithmica (New York)
Volume38
Issue number4
DOIs
StatePublished - Jan 1 2004

Keywords

  • Approximation algorithms
  • Broadcasting
  • Scheduling

ASJC Scopus subject areas

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

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

Cite this