@inproceedings{5b16dbc69e3f4ebeb2f3f65c7f1a901d,
title = "Algorithms for minimizing response time in broadcast scheduling",
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.",
author = "Rajiv Gandhi and Samir Khuller and Kim, {Yoo Ah} and Wan, {Yung Chun}",
year = "2002",
doi = "10.1007/3-540-47867-1_30",
language = "English (US)",
isbn = "9783540478676",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "425--438",
editor = "Cook, {William J.} and Schulz, {Andreas S.}",
booktitle = "Integer Programming and Combinatorial Optimization - 9th International IPCO 2002 Conference, Proceedings",
address = "Germany",
note = "9th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2002 ; Conference date: 27-05-2002 Through 29-05-2002",
}