کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
430203 | 687926 | 2016 | 17 صفحه PDF | دانلود رایگان |
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⊆EM⊆E such that every vertex in U is incident to exactly one edge in M. The load of a server v∈Vv∈V is defined as (degM(v)+12), 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|)Ω(|V|) rounds are needed and propose distributed deterministic approximation algorithms for the problem. It yields 2-approximation and has time complexity O(Δ5)O(Δ5), where Δ is the maximum degree in V. We also give some greedy algorithms.
Journal: Journal of Computer and System Sciences - Volume 82, Issue 8, December 2016, Pages 1251–1267