Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Approximate majorization and fair online load balancing

Approximate majorization and fair online load balancing This article relates the notion of fairness in online routing and load balancing to vector majorization as developed by Hardy et al. 1929. We define α -supermajorization as an approximate form of vector majorization, and show that this definition generalizes and strengthens the prefix measure proposed by Kleinberg et al. 2001 as well as the popular notion of max-min fairness .The article revisits the problem of online load-balancing for unrelated 1-∞ machines from the viewpoint of fairness. We prove 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 . This may be contrasted with polynomial lower bounds presented by Goel et al. 2001 for fair online routing.We also define a machine-centric view of fairness using the related concept of submajorization . We prove that the greedy online algorithm is globally O (log m )- balanced , where m is the number of machines. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Algorithms (TALG) Association for Computing Machinery

Approximate majorization and fair online load balancing

Download PDF
12 pages

Loading next page...
 
/lp/association-for-computing-machinery/approximate-majorization-and-fair-online-load-balancing-oJWO6t7kS9
Publisher
Association for Computing Machinery
Copyright
Copyright © 2005 by ACM Inc.
ISSN
1549-6325
DOI
10.1145/1103963.1103970
Publisher site
See Article on Publisher Site

Abstract

This article relates the notion of fairness in online routing and load balancing to vector majorization as developed by Hardy et al. 1929. We define α -supermajorization as an approximate form of vector majorization, and show that this definition generalizes and strengthens the prefix measure proposed by Kleinberg et al. 2001 as well as the popular notion of max-min fairness .The article revisits the problem of online load-balancing for unrelated 1-∞ machines from the viewpoint of fairness. We prove 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 . This may be contrasted with polynomial lower bounds presented by Goel et al. 2001 for fair online routing.We also define a machine-centric view of fairness using the related concept of submajorization . We prove that the greedy online algorithm is globally O (log m )- balanced , where m is the number of machines.

Journal

ACM Transactions on Algorithms (TALG) – Association for Computing Machinery

Published: Oct 1, 2005

There are no references for this article.