Dec 08:  A little bit of help goes a long way: online scheduling  with \eps resource augmentation
               Chandra Chekuri.
                  Bell Labs.
 
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.
--------------------------------------------------------------------------