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 journalConference articlepeer-review

18 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. 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)
Pages (from-to)425-438
Number of pages14
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2337 LNCS
StatePublished - Dec 1 2002
Event9th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2002 - Cambridge, MA, United States
Duration: May 27 2002May 29 2002

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

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

Cite this