%0 Journal Article
%J Operations Research Letters
%D 2004
%T Equivalence of two linear programming relaxations for broadcast scheduling
%A Khuller, Samir
%A Kim,Yoo-Ah
%K Approximation algorithms
%K Broadcasting
%K Linear programming
%K scheduling
%X A server needs to compute a broadcast schedule for n pages whose request times are known in advance. Outputting a page satisfies all outstanding requests for the page. The goal is to minimize the average waiting time of a client. In this paper, we show the equivalence of two apparently different relaxations that have been considered for this problem.
%B Operations Research Letters
%V 32
%P 473 - 478
%8 2004/09//
%@ 0167-6377
%G eng
%U http://www.sciencedirect.com/science/article/pii/S016763770300169X
%N 5
%R 10.1016/j.orl.2003.11.012