Title: A little bit of help goes a long way: online scheduling with \eps resource augmentation.
Speaker: Chandra Chekuri, Bell Labs
Date: December 8, 2003 3:30-4:30pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
We consider online scheduling of jobs on parallel machines with goal of minimizing average response time and several related measures. We prove that simple and natural algorithms have constant competitiveness if the online algorithm is given arbitrarily small advantage over the adversary. The advantage is in having either slightly faster machines or in having a few more machines.
Joint work with Ashish Goel, Sanjeev Khanna, and Amit Kumar.