Kolloquiumsvortrag: Prof. Dr. Naveen Garg, Department of Computer Science, Indian Institute of Technology, Delhi, India.
27.06.2014 von 14:15 bis 15:30
Institut für Informatik, Ludewig-Meyn-Str. 2, Übungsraum 2
Titel: Scheduling with Resource Augmentation
Abstract:
We consider the problem of scheduling jobs in an online manner so as to minimize the average response time. For the unrelated machines model there is no online algorithm possible which has bounded competitive ratio. To get around this researchers have proposed a resource augmentation model where it is assumed that the machines of the online algorithm are slightly faster than those of the offline adversary. In this model we show that a natural greedy algorithm is constant-competitive. The algorithm is analyzed using a dual-fitting approach.