On the distributed complexity of the semi-matching problem

详细信息    查看全文

• 作者：Andrzej Czygrinow^a ; ^{andrzej.czygrinow@asu.edu" class="auth_mail" title="E-mail the corresponding author} ; Michał Hanćkowiak^b ; ^{mhanckow@amu.edu.pl" class="auth_mail" title="E-mail the corresponding author} ; Edyta Szymańska^b ; ^{edka@amu.edu.pl" class="auth_mail" title="E-mail the corresponding author} ; Wojciech Wawrzyniak^b ; ^{wwawrzy@amu.edu.pl" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Distributed algorithms ; Semi-matching
• 刊名：Journal of Computer and System Sciences
• 出版年：2016
• 出版时间：December 2016
• 年：2016
• 卷：82
• 期：8
• 页码：1251-1267
• 全文大小：631 K

文摘

We consider the problem of matching clients with servers, each of which can process a subset of clients. It is known as the semi-matching or load balancing   problem in a bipartite graph G=(V,U,E)$G=(V,U,E)$, where U corresponds to the clients and V   to the servers. The goal is to find a set of edges M⊆E$M\subseteq E$ such that every vertex in U is incident to exactly one edge in M. The load   of a server v∈V$v\in V$ is defined as $\left(\begin{array}{c}{\mathrm{deg}}_M(v)+1\\ 2\end{array}\right)$, and the problem is to find a semi-matching M   that minimizes the sum of the loads of the servers. We show that to find an optimal solution in a distributed setting Ω(|V|)$\mathrm{\Omega }(|V|)$ rounds are needed and propose distributed deterministic approximation algorithms for the problem. It yields 2-approximation and has time complexity O(Δ⁵)$O\left({\mathrm{\Delta }}^5\right)$, where Δ is the maximum degree in V. We also give some greedy algorithms.