On-line load balancing made simple: greedy strikes back

DOI10.1016/J.JDA.2006.02.001zbMath1137.68062OpenAlexW2116838521MaRDI QIDQ924556

Giorgio Gambosi, Gaia Nicosia, Walter Unger, Paolo Penna, Pierluigi Crescenzi

Publication date: 16 May 2008

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2006.02.001

zbMATH Keywords

computational complexityapproximation algorithmon-line algorithmload balancing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Approximation algorithms (68W25)

Related Items (3)

Improved algorithms for online load balancing ⋮ An Equivalent Version of the Caccetta-Häggkvist Conjecture in an Online Load Balancing Problem ⋮ Online scheduling of jobs with favorite machines

Cites Work

• Unnamed Item
• An improved lower bound for load balancing of tasks with unknown duration
• Approximation algorithms for scheduling unrelated parallel machines
• On-line load balancing
• On-line load balancing and network flow
• On-line algorithms for the channel assignment problem in cellular networks.
• On-Line Load Balancing in a Hierarchical Server Topology
• On-Line Load Balancing of Temporary Tasks
• The Competitiveness of On-Line Assignments
• On-Line Load Balancing of Temporary Tasks on Identical Machines
• Über ein Paradoxon aus der Verkehrsplanung
• Bounds for Certain Multiprocessing Anomalies

This page was built for publication: On-line load balancing made simple: greedy strikes back