Name
Abstract | ||
|---|---|---|
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 ) , where U corresponds to the clients and V to the servers. The goal is to find a set of edges M ¿ E such that every vertex in U is incident to exactly one edge in M. The load of a server v ¿ V is defined as ( deg M ¿ ( v ) + 1 2 ) , 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 | ) rounds are needed and propose distributed deterministic approximation algorithms for the problem. It yields 2-approximation and has time complexity O ( Δ 5 ) , where Δ is the maximum degree in V. We also give some greedy algorithms. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1016/j.jcss.2016.05.001 | J. Comput. Syst. Sci. |
Keywords | Field | DocType |
Distributed algorithms,Semi-matching | Discrete mathematics,Approximation algorithm,Combinatorics,Vertex (geometry),Server,Bipartite graph,Greedy algorithm,Distributed algorithm,Degree (graph theory),Time complexity,Mathematics | Journal |
Volume | Issue | ISSN |
82 | 8 | 0022-0000 |
Citations | PageRank | References |
0 | 0.34 | 6 |
Authors | ||
6 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andrzej Czygrinow | 1 | 227 | 25.81 |
| Michal Hanćkowiak | 2 | 81 | 6.66 |
| Edyta Szymanska | 3 | 46 | 5.53 |
| Wojciech Wawrzyniak | 4 | 97 | 8.23 |
| HanćkowiakMichał | 5 | 0 | 0.34 |
| SzymańskaEdyta | 6 | 0 | 0.34 |