| Author: | Patchrawat Uthaisombut |
| Advisor: | Dr. Eric Torng |
| Email: | uthaisom@cse.msu.edu; http://www.cse.msu.edu/~uthaisom |
Previously, extra-resource analysis has been used to argue that certain on-line algorithms are good choices for solving specific problems because these algorithms perform well with respect to the optimal off-line algorithm when given extra resources. We now introduce a new application for extra-resource analysis: deriving a qualitative divergence between off-line and on-line algorithms. We do this for the load balancing problem, the problem of assigning a list of jobs on m identical machines to minimize the makespan, the maximum load on any machine. We analyze the worst-case performance of on-line and off-line approximation algorithms relative to the performance of the optimal off-line algorithm when the approximation algorithms have k extra machines. Our main results are the following: The Longest-Processing-Time (LPT) algorithm will produce a schedule with makespan no larger than that of the optimal off-line algorithm if LPT has at least (4m-1)/3 machines while the optimal off-line algorithm has m machines. In contrast, no on-line algorithm can guarantee the same with any number of extra machines.
Return to Workshop Listing