Equivalence of two linear programming relaxations for broadcast scheduling
| Title | Equivalence of two linear programming relaxations for broadcast scheduling |
| Publication Type | Journal Articles |
| Year of Publication | 2004 |
| Authors | Khuller S, Kim Y-A |
| Journal | Operations Research Letters |
| Volume | 32 |
| Issue | 5 |
| Pagination | 473 - 478 |
| Date Published | 2004/09// |
| ISBN Number | 0167-6377 |
| Keywords | Approximation algorithms, Broadcasting, Linear programming, scheduling |
| Abstract | 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. |
| URL | http://www.sciencedirect.com/science/article/pii/S016763770300169X |
| DOI | 10.1016/j.orl.2003.11.012 |