Load Balancing White Papers
Approximate Majorization and Fair Online Load Balancing
Overview This paper relates the notion of fairness in online routing and load balancing to vector majorization as developed by Hardy, Littlewood, and Polya. It define -supermajorization as an approximate form of vector majorization, and show that this definition generalizes and strengthens the prefix measure proposed by Kleinberg, Rabani and Tardos as well as the popular notion of max-min fairness. The paper revisits the problem of online load-balancing for unrelated 1- ý!, machines from the viewpoint of fairness. It proves that a greedy approach is O(log n)-supermajorized by all other allocations, where n is the number of jobs. This means the greedy approach is globally O(log n)- fair.
| Publisher | Stanford University | File Format | |
|---|---|---|---|
| Date Published | September 2004 | ||
| Format | White Papers | ||
| Topics | |||
-
Did you find this white paper useful? 0 out of 1 users found this white paper useful
White Paper RSS
Download
Register
