skip to main content
10.1145/1148109.1148159acmconferencesArticle/Chapter ViewAbstractPublication PagesspaaConference Proceedingsconference-collections
Article

Fair online load balancing

Published: 30 July 2006 Publication History

Abstract

We revisit from a fairness point of view the problem of online load balancing in the restricted assignment model and the 1-∞ model. We consider both a job-centric and a machine-centric view of fairness, as proposed by Goel et al. [11]. These notions are equivalent to the approximate notion of prefix competitiveness proposed by Kleinberg, Rabani and Tardos [14], as well as to the notion of approximate majorization, and they generalize the well studied notion of max-min fairness.We resolve a question posed by Goel,Meyerson and Plotkin [11] proving that the greedy strategy is globally O(logm)-fair, where m denotes the number of machines. This result improves upon the analysis of [11] who showed that the greedy strategy is globally O(log n)-fair, where n is the number of jobs. Typically, n > m, and therefore our improvement is significant. Our proof matches the known lower bound for the problem with respect to the measure of global fairness.The improved bound is obtained by analyzing, in a more accurate way, the more general restricted assignment model studied previously in [6]. We provide an alternative bound which is not worse than the bounds of [6], and it is strictly better in many cases. The bound we prove is, in fact, much more general and it bounds the load on any prefix of most loaded machines. As a corollary from this more general bound we get that the greedy algorithm results in an assignment that is globally O(logm)-balanced. The last result generalizes the previous result of [11] who proved that the greedy algorithm yields an assignment that is globally O(logm)-balanced for the 1-∞ model.

References

[1]
Miriam Allalouf and Yuval Shavitt. Maximum flow routing with weighted max-min fairness. In First International Workshop on QoS Routing (WQoSR), 2004.
[2]
J. A. Aslam, A. Rasala, C. Stein, and N. Young. Improved bicriteria existence theorems for scheduling. In SODA: ACM-SIAM Symposium on Discrete Algorithms, pages 846--847, 1999.
[3]
James Aspnes, Yossi Azar, Amos Fiat, Serge Plotkin, and Orli Waarts. On-line routing of virtual circuits with applications to load balancing and machine scheduling. J. ACM, 44(3):486--504, 1997.
[4]
Yossi Azar. On-line load balancing. Online Algorithms - The State of the Art, Springer, (8):178--195, 1998.
[5]
Yossi Azar, Leah Epstein, Yossi Richter, and Gerhard J. Woeginger. All-norm approximation algorithms. J. Algorithms, 52(2):120--133, 2004.
[6]
Yossi Azar, Joseph Naor, and Raphael Rom. The competitiveness of on-line assignments. Journal of Algorithms, 18:221--237, 1995.
[7]
Dimitri Bertsekas and Robert Gallager. Data networks. Prentice-Hall, Inc., 1987.
[8]
N. Buchbinder and J. Naor. A primal-dual approach to online routing and packing. In Manuscript, 2006.
[9]
John E. Littlewood Godfrey H. Hardy and George P'olya. Some simple inequalities satisfied by convex functions. In Messenger Math, pages 58:145--152, 1929.
[10]
Ashish Goel and Adam Meyerson. Simultaneous optimization via approximate majorization for concave profits or convex costs. 2005.
[11]
Ashish Goel, Adam Meyerson, and Serge A. Plotkin. Approximate majorization and fair online load balancing. In Symposium on Discrete Algorithms, pages 384--390, 2001.
[12]
Ashish Goel, Adam Meyerson, and Serge A. Plotkin. Combining fairness with throughput: Online routing with multiple objectives. J. Comput. Syst. Sci., 63(1):62--79, 2001.
[13]
J.M. Jaffe. Bottleneck flow control. IEEE Transactions on Communications, 29(7):954--962, 1981.
[14]
Jon Kleinberg, Eva Tardos, and Yuval Rabani. Fairness in routing and load balancing. In FOCS '99: Proceedings of the 40th Annual Symposium on Foundations of Computer Science, page 568, 1999.
[15]
Amit Kumar and Jon M. Kleinberg. Fairness measures for resource allocation. In IEEE Symposium on Foundations of Computer Science, pages 75--85, 2000.
[16]
R. K. lain, Dab-Ming Chiu, and William Howe. A quantitative measure of fairness and discrimination for resource allocation in shared systems. In DEC Res. Rep. TR-301, 1984.
[17]
A. W. Marshal and I. Olkin. Inequalities: Theory of majorization and its applications. In volume 143 of Mathematics in Science and Engineering. Academic Press, New York, 1979.
[18]
Clifford Stein and Joel Wein. On the existence of schedules that are near-optimal for both makespan and total weighted completion time. Technical Report TR96-295, 1996.

Cited By

View all
  • (2024)Online Load and Graph Balancing for Random Order InputsProceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3626183.3659983(491-497)Online publication date: 17-Jun-2024
  • (2021)Learning to Assign: Towards Fair Task Assignment in Large-Scale Ride HailingProceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining10.1145/3447548.3467085(3549-3557)Online publication date: 14-Aug-2021
  • (2019)Rejecting jobs to minimize load and maximum flow-timeJournal of Computer and System Sciences10.1016/j.jcss.2017.07.00691:C(42-68)Online publication date: 1-Jan-2019
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
SPAA '06: Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures
July 2006
344 pages
ISBN:1595934529
DOI:10.1145/1148109
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 30 July 2006

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. competitive analysis
  2. greedy algorithm
  3. load balancing
  4. online algorithms
  5. scheduling

Qualifiers

  • Article

Conference

SPAA06
SPAA06: 18th ACM Symposium on Parallelism in Algorithms and Architectures 2006
July 30 - August 2, 2006
Massachusetts, Cambridge, USA

Acceptance Rates

Overall Acceptance Rate 447 of 1,461 submissions, 31%

Upcoming Conference

SPAA '25
37th ACM Symposium on Parallelism in Algorithms and Architectures
July 28 - August 1, 2025
Portland , OR , USA

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)18
  • Downloads (Last 6 weeks)1
Reflects downloads up to 27 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2024)Online Load and Graph Balancing for Random Order InputsProceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3626183.3659983(491-497)Online publication date: 17-Jun-2024
  • (2021)Learning to Assign: Towards Fair Task Assignment in Large-Scale Ride HailingProceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining10.1145/3447548.3467085(3549-3557)Online publication date: 14-Aug-2021
  • (2019)Rejecting jobs to minimize load and maximum flow-timeJournal of Computer and System Sciences10.1016/j.jcss.2017.07.00691:C(42-68)Online publication date: 1-Jan-2019
  • (2018)Pricing for FairnessAlgorithmica10.5555/3118226.311847057:4(873-892)Online publication date: 31-Dec-2018
  • (2018)The Efficiency of Fair DivisionTheory of Computing Systems10.1007/s00224-011-9359-y50:4(589-610)Online publication date: 25-Dec-2018
  • (2015)Rejecting jobs to minimize load and maximum flow-timeProceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms10.5555/2722129.2722204(1114-1133)Online publication date: 4-Jan-2015
  • (2014)Price-based protocols for fair resource allocationACM Transactions on Algorithms10.1145/255694910:2(1-14)Online publication date: 1-Feb-2014
  • (2014)Fair energy-efficient sensing task allocation in participatory sensing with smartphonesIEEE INFOCOM 2014 - IEEE Conference on Computer Communications10.1109/INFOCOM.2014.6848070(1366-1374)Online publication date: Apr-2014
  • (2014)Simultaneous Approximation of Multi-criteria Submodular Function MaximizationJournal of the Operations Research Society of China10.1007/s40305-014-0053-z2:3(271-290)Online publication date: 7-Sep-2014
  • (2013)Online Multidimensional Load BalancingApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques10.1007/978-3-642-40328-6_21(287-302)Online publication date: 2013
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media