Approximate majorization and fair online load balancing
Ashish Goel, Adam Meyerson, Serge A. Plotkin · 2001
This paper revisits the greedy online load-balancing algorithm for unrelated 1-1 machines from the viewpoint of fairness. We prove that the greedy approach is globally O(log n)-fair where n is the number of jobs. This should be contrasted with polynomial lower bounds presented in [7] for the routing model in which a single job may require multiple resources. We measure fairness via the notion of vector majorization as developed by Hardy, Littlewood, and Polya [13]. Our definition of fairness in terms of approximate majorization is equivalent to the prefix measure proposed by Kleinberg, Rabani, and Tardos [11]. Approximate majorization generalizes the popular notion of max-min fairness to account for the variable allocation of jobs to machines [11, 7]. We also define a machine-centric view of fairness and prove that the greedy online algorithm is globally O(log m)-balanced, where m is the number of machines.