Equivalence of two linear programming relaxations for broadcast scheduling |
| |
| Authors: | Samir Khuller Yoo-Ah Kim |
| |
| Affiliation: | Algorithms and Theory Group, Department of Computer Science and Institute for Advanced Computer Studies, University of Maryland, A.V. Williams Building, Room 3369, College Park, MD 20742, USA |
| |
| 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. |
| |
| Keywords: | Scheduling Broadcasting Approximation algorithms Linear programming |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
