Vi överväger belastningsbalans i följande inställning. Den on-line algoritmen är tillåten att använda n maskiner, medan den optimala offline algoritmen är begränsad till m maskiner, för vissa fasta m < n. Vi visar att medan den giriga algoritmen har ett konkurrensförhållande som sönderfaller linjärt i inversen av n/m, den bästa on-line algoritmen har ett förhållande som sönderfaller exponentiellt i n/m. Specifikt ger vi en algoritm med ett konkurrensförhållande på 1 + 2 − n m (1‐o(1)) och en lägre gräns på 1 + e − n m (1+o(1)) på konkurrensförhållandet för eventuella randomiserade algoritmer. Vi betraktar också det förebyggande fallet. Vi visar en on-line algoritm med ett konkurrenskraftigt förhållande på 1 + e − n m (1+o(1)). Vi visar att algoritmen är optimal genom att visa en matchande lägre gräns. Vi överväger också den icke förebyggande modellen med tillfälliga uppgifter. Vi bevisar att för n = m + 1, är den giriga algoritmen optimal. (Det är inte optimalt för permanenta uppgifter.)
Azar m.fl. REF visade ett konkurrensförhållande på 1 + 1/2 n m (1‐o(1)) när online-algoritmen är tillåten att använda n identiska maskiner medan offline optimal är begränsad till m < n identiska maskiner.
Resource Augmentation in Load Balancing
{'venue': 'Algorithm Theory - SWAT 2000, 7th Scandinavian Workshop on Algorithm Theory, Proceedings, volume 1851 of Lecture Notes in Computer Science', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}