Slide 4 of 47
Notes:
Here is one intuition for this result: Each of R resources on each machine begins with $1. Assume wolog that the optimal algorithm uses at most 1/(log n) of each resource.
We greedily make assignment ai to machine m(ai). The optimal algorithm assigns the relevant job to machine m(ai)’. The cost to assign the job to m(ai) = the cost to assign the job to m(ai)’ = S resource costs for assigning the job to m(ai)’ = S Ur * the current cost for resource r on m(ai)’, for some resource-dependent Ur.
For each resource r on m(ai)’, we take away a fraction Ur of the resource’s money. We give this to m(ai) to “pay” for assignment ai. We pay each resource a sum equal to ai’s cost for that resource, throwing away anything left over.
The offline algorithm uses less than a (1/log n) slice of each resource altogether. Such a slice costs exactly as much as all the other jobs on the machine combined. So resources never give away more money than they have. Moreover, the sum of the Ur’s over time, for a given resource, totals at most 1. If a machine has $10 and gives away $3, it never gives away more than 70% of its wealth in the future. This means it never has to spend the same coin or bill twice. We assume it does not.
The system had $nR worth of load originally. A machine can receive up to $nR, give it away, and receive it back again. This money pays for jobs with total cost = 2nR. No resource ever has more than log 2nR times the load of the optimal algorithm’s.
For a full proof, see J. Aspnes, Y. Azar, A. Fiat, S. Plotkin and O. Waarts, “On-Line Routing of Virtual Circuits with Applications to Load Balancing and Machine Scheduling,” Journal of the ACM, Vol. 44, No. 3, pages 486-504, May 1997
