TY - CONF
T1 - A robust maximum completion time measure for scheduling
T2 - Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm
Y1 - 2006
A1 - Charikar,Moses
A1 - Khuller, Samir
AB - One popular measure for evaluating the performance of scheduling algorithms, is the maximum response time of any job (makespan). Typically the objective is to find a schedule that minimizes the maximum response time over all jobs. One drawback of this measure is that a relatively small number of jobs in the request set could cause the maximum response time to be very high. Thus, this measure reflects local rather than global properties of the request set. In this paper we consider a robust generalization of this measure. Our goal is to minimize T, such that a given fraction of jobs can be scheduled with a response time of at most T. We demonstrate the applicability of this measure in the context of broadcast scheduling. We show that in the online setting no constant factor online approximation is possible for the problem of minimizing the maximum response time for a given fraction of jobs in the context of broadcast scheduling. We give a factor 5, polynomial time offline approximation algorithm for the problem of minimizing the maximum response time for a given fraction of jobs in the context of broadcast scheduling.
JA - Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm
T3 - SODA '06
PB - ACM
CY - New York, NY, USA
SN - 0-89871-605-5
UR - http://doi.acm.org/10.1145/1109557.1109594
M3 - 10.1145/1109557.1109594
ER -