Speaker: Yoo-Ah Kim
Day:  Wednesday, 3/22/2006
Room: ITEB 336
Time: 3:30pm
Title: A robust maximum completion time measure for scheduling

One popular measure  for evaluting 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, the authors consider a robust generalization of this measure.  The goal is to minimize T, such that a given fraction of jobs can be scheduled with a response time of at most T. The paper demonstrates the applicability of this measure in the context of broadcast scheduling. They give a factor 5, polynomial time approximation algorithm for the problem of minimizing the maximum response time for a given fraction of jobs in the context of broadcast scheduling.

This is work of Moses Charikar, Samir Khuller from SODA 2006.