Ancient and new algorithms for load balancing in the Lp norm.
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F01%3A05025167" target="_blank" >RIV/67985840:_____/01:05025167 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
Ancient and new algorithms for load balancing in the Lp norm.
Original language description
We consider the on-line load balancing problem where there are $m$ identical machines the goal is to minimize the sum (over all machines) of the squares of the loads, instead of the traditional maximum load. We show that for the sum of the squares the greedy algorithm performs within $4/3$ of the optimum, and no on-line algorithm achieves a better competitive ratio. Interestingly, we show that the performance of greedy is not monotone in the number of machines.
Czech name
—
Czech description
—
Classification
Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BA - General mathematics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/IAA1019602" target="_blank" >IAA1019602: Arithmetic, proof theory and complexity theory</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)
Others
Publication year
2001
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Algorithmica
ISSN
0178-4617
e-ISSN
—
Volume of the periodical
29
Issue of the periodical within the volume
3
Country of publishing house
US - UNITED STATES
Number of pages
20
Pages from-to
422-441
UT code for WoS article
—
EID of the result in the Scopus database
—