Scholarlink

<p>We study the classical load balancing problem in a fully dynamic setting where jobs both arrive and depart. Each job can only be assigned to a subset of machines and can be reassigned at any time step. The goal is to maintain a near-optimal maximum load at all time steps with a small total number of reassignments. We consider the setting where the degree of the jobs (number of machines they can be assigned to) is bounded. This is motivated by natural settings where jobs can only be locally assigned to a small number of machines (e.g., bike sharing [<CitationRef CitationID="CR12">12</CitationRef>], map-reduce settings [<CitationRef CitationID="CR23">23</CitationRef>]) and generalizes the classical <span>EdgeOrientation</span> problem. We give a constant competitive algorithm with amortized constant number of reassignments. We also consider the generalizations of our problem to arbitrary reassignment costs and arbitrary job sizes. The generalizations require different techniques and we give a different randomized algorithm for these.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Fully-Dynamic Load Balancing

  • 期刊论文

  • 发表日期：

    2025年12月10日

查看全文
  • Ayoub Foussoul,
  • Vineet Goyal,
  • Amit Kumar

摘要

We study the classical load balancing problem in a fully dynamic setting where jobs both arrive and depart. Each job can only be assigned to a subset of machines and can be reassigned at any time step. The goal is to maintain a near-optimal maximum load at all time steps with a small total number of reassignments. We consider the setting where the degree of the jobs (number of machines they can be assigned to) is bounded. This is motivated by natural settings where jobs can only be locally assigned to a small number of machines (e.g., bike sharing [12], map-reduce settings [23]) and generalizes the classical EdgeOrientation problem. We give a constant competitive algorithm with amortized constant number of reassignments. We also consider the generalizations of our problem to arbitrary reassignment costs and arbitrary job sizes. The generalizations require different techniques and we give a different randomized algorithm for these.