Simultaneously Load Balancing for Every p-norm, With Reassignments
Simultaneously Load Balancing for Every p-norm, With Reassignments
复制标题
通过重新分配对每个 p 范数同时进行负载平衡
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
C. Stein
中科院分区：
文献类型：
--
作者：
A. Bernstein;T. Kopelowitz;Seth Pettie;E. Porat;C. Stein
本文研究了负载均衡任务，其目标函数是在静态和增量设置下，对于\(p\geq1\)，最小化负载的\(p\)-范数。我们考虑两个密切相关的负载均衡问题。在二分匹配问题中，给定一个二分图\(G=(C\cup S, E)\)，目标是将每个客户端\(c\in C\)分配给一个服务器\(s\in S\)，以使\(S\)上分配负载的\(p\)-范数最小化。
在图定向问题中，目标是对给定无向图的边进行定向（指定方向），同时最小化出度的\(p\)-范数。图定向问题是二分匹配问题的一个特殊情况，但不太复杂，这导致了更简单的算法。
对于图定向问题，我们表明著名的千叶 - 西泽剥皮算法提供了一种简单的线性时间负载均衡方案，其输出是一种定向，对于所有\(p\geq1\)，在\(p\)-范数意义下是\(2\)-竞争的。对于二分匹配问题，我们首先提供一种离线算法来计算最优分配。然后我们将此解决方案扩展到带有重新分配的在线二分匹配问题，其中\(C\)中的顶点与其相应的边以在线方式到达，并且每当一个新顶点到达时，我们允许重新分配\(C\)中平摊\(O(1)\)个顶点。在这种在线场景下，我们展示了如何维护一种单一分配，对于所有\(p\geq1\)，在\(p\)-范数意义下是\(8\)-竞争的。
This paper investigates the task of load balancing where the objective function is to minimize the p-norm of loads, for p\geq 1, in both static and incremental settings. We consider two closely related load balancing problems. In the bipartite matching problem we are given a bipartite graph G=(C\cup S, E) and the goal is to assign each client c\in C to a server s\in S so that the p-norm of assignment loads on S is minimized.
In the graph orientation problem the goal is to orient (direct) the edges of a given undirected graph while minimizing the p-norm of the out-degrees. The graph orientation problem is a special case of the bipartite matching problem, but less complex, which leads to simpler algorithms.
For the graph orientation problem we show that the celebrated Chiba-Nishizeki peeling algorithm provides a simple linear time load balancing scheme whose output is an orientation that is 2-competitive, in a p-norm sense, for all p\geq 1. For the bipartite matching problem we first provide an offline algorithm that computes an optimal assignment. We then extend this solution to the online bipartite matching problem with reassignments, where vertices from C arrive in an online fashion together with their corresponding edges, and we are allowed to reassign an amortized O(1) vertices from C each time a new vertex arrives. In this online scenario we show how to maintain a single assignment that is 8-competitive, in a p-norm sense, for all p\geq 1.
在线 MST 和 TSP 的追索权
DOI：
10.1137/130917703
发表时间：
--
期刊：
SIAM J. Comput.
影响因子：
--
作者：
N. Megow;M. Skutella;J. Verschae;A. Wiese.
通讯作者：
A. Wiese.