论文标题
提高分布式负载平衡的界限
Improved Bounds for Distributed Load Balancing
论文作者
论文摘要
在负载平衡问题中，输入为$ n $ vertex二分图$ g =（c \ cup s，e）$，每个客户的$ c \ in c $ in C $。该算法必须将C $中的每个客户端$ C \分配给相邻服务器$ s \ in S $。然后，服务器的负载是分配给其的所有客户端的加权总和，目标是计算一个分配，以最大程度地减少服务器负载的某些功能，通常是最大服务器负载（即$ \ ell _ {\ elfty} $ - norm）或$ \ ell_p $ - 服务器负载的$ \ ell_p $。 我们在分布式设置中研究负载平衡。拥塞模型中有两个现有结果。 Czygrinow等。 [DISC 2012]显示了具有圆形复杂性$ O（δ^5）$的未加权客户的2个附属能力，其中$δ$是输入图的最大程度。 Halldórsson等。 [SPAA 2015]显示了一个$ o（\ log {n}/\ log \ log {n}）$ - 近似未加权的客户端和$ o（\ log^2 \！{n}/\ log \ log \ log \ log {n}）$ - 适用于具有圆型polylog $（n）$（n）$（n）$（n）$的加权客户的近似客户。 在本文中，我们显示了第一个分布式算法，以计算Polylog $（n）$ roughs中的负载平衡问题的$ O（1）$ - 近似。在Escest模型中，我们为未加权客户提供了Polylog $（n）$回合的$ O（1）$ - 近似算法。对于加权客户端，近似值为$ O（\ log {n}）$。在较少约束的本地模型中，我们为Polylog $（n）$ rounds中的加权客户提供了$ O（1）$ - 近似算法。 我们的方法还对标准顺序设置也有影响，在该设置中，我们获得了第一个$ O（1）$ - 在接近线性时间内运行的此问题的近似值。已经知道了2个附属物，但是它需要求解线性程序，因此要慢得多。最后，我们注意到我们的所有结果同时近似所有$ \ ell_p $ -norms，包括$ \ ell _ {\ infty} $ - norm-norm。
In the load balancing problem, the input is an $n$-vertex bipartite graph $G = (C \cup S, E)$ and a positive weight for each client $c \in C$. The algorithm must assign each client $c \in C$ to an adjacent server $s \in S$. The load of a server is then the weighted sum of all the clients assigned to it, and the goal is to compute an assignment that minimizes some function of the server loads, typically either the maximum server load (i.e., the $\ell_{\infty}$-norm) or the $\ell_p$-norm of the server loads. We study load balancing in the distributed setting. There are two existing results in the CONGEST model. Czygrinow et al. [DISC 2012] showed a 2-approximation for unweighted clients with round-complexity $O(Δ^5)$, where $Δ$ is the maximum degree of the input graph. Halldórsson et al. [SPAA 2015] showed an $O(\log{n}/\log\log{n})$-approximation for unweighted clients and $O(\log^2\!{n}/\log\log{n})$-approximation for weighted clients with round-complexity polylog$(n)$. In this paper, we show the first distributed algorithms to compute an $O(1)$-approximation to the load balancing problem in polylog$(n)$ rounds. In the CONGEST model, we give an $O(1)$-approximation algorithm in polylog$(n)$ rounds for unweighted clients. For weighted clients, the approximation ratio is $O(\log{n})$. In the less constrained LOCAL model, we give an $O(1)$-approximation algorithm for weighted clients in polylog$(n)$ rounds. Our approach also has implications for the standard sequential setting in which we obtain the first $O(1)$-approximation for this problem that runs in near-linear time. A 2-approximation is already known, but it requires solving a linear program and is hence much slower. Finally, we note that all of our results simultaneously approximate all $\ell_p$-norms, including the $\ell_{\infty}$-norm.
