%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