论文标题
改进的在线负载平衡算法
Improved algorithms for online load balancing
论文作者
论文摘要
我们考虑在线负载平衡问题及其在重复游戏框架中的扩展。在每个回合中，玩家都会在$ k $服务器上选择一个分布（任务分配），然后环境揭示了每个服务器的负载，这确定了每个服务器的计算时间用于处理分配的任务。毕竟，播放器的成本是通过累积计算时间向量的某些规范来衡量的。如果规范为$ l_ \ infty $ -norm，则成本是Makepan。目的是最大程度地减少遗憾，即，相对于事后最佳固定分布的成本，将玩家的成本降至最低。我们提出了有关一般规范的算法，并证明了它们的遗憾界限。特别是，对于$ l_ \ infty $ norm，我们的遗憾界限与最著名的界限匹配，并且拟议的算法在每次试验中运行，涉及线性编程和二阶编程，而尚无多项式时间算法以前曾被众所周知。
We consider an online load balancing problem and its extensions in the framework of repeated games. On each round, the player chooses a distribution (task allocation) over $K$ servers, and then the environment reveals the load of each server, which determines the computation time of each server for processing the task assigned. After all rounds, the cost of the player is measured by some norm of the cumulative computation-time vector. The cost is the makespan if the norm is $L_\infty$-norm. The goal is to minimize the regret, i.e., minimizing the player's cost relative to the cost of the best fixed distribution in hindsight. We propose algorithms for general norms and prove their regret bounds. In particular, for $L_\infty$-norm, our regret bound matches the best known bound and the proposed algorithm runs in polynomial time per trial involving linear programming and second order programming, whereas no polynomial time algorithm was previously known to achieve the bound.
