## Brief announcement: Distributed approximations for the semi-matching problem

### Authors:

- Andrzej Czygrinow,
- Michał Hanćkowiak,
- Krzysztof Krzywdziński,
- Edyta Barbara Szymańska,
- Wojciech Wawrzyniak

### Abstract

We consider the semi-matching problem in bipartite graphs. The network is represented by a bipartite graph G = (U ∪ V, E), where U corresponds to clients, V to servers, and E is the set of available connections between them. 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 the square of its degree in M and the problem is to find an optimal semi-matching, i.e. a semi-matching that minimizes the sum of the loads of the servers. Formally, given a bipartite graph G = ∪ V,E), a semi-matching in G is a subgraph M such that deg _{M} (u) = 1 for every u ε U. A semi-matching M is called optimal if cost(M): = Σ _{v ε V} (deg _{M} (v))^{2} is minimal. It is not difficult to see that for any semi-matching M, where Δ is such that max _{v ε V} d(v) ≤ Δ. Consequently, if M* is optimal and M is arbitrary, then cost (M) ≤ Δ|V|cost(M*)/|U|. Our main result shows that in some networks the Δ|V|/|U| factor can be reduced to a constant (Theorem 1). © 2011 Springer-Verlag.

- Record ID
- UAM52e591b554b44587a4f8dcc3d9b8d77a
- Author
- Pages
- 200-201
- Book
- Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Lecture Notes in Computational Vision and Biomechanics, 2011, 200-201 p., ISBN 9783642240997
- ASJC Classification
- ; ; ; ; ; ; ;
- DOI
- DOI:10.1007/978-3-642-24100-0_18 opening in a new tab
- Language
- en English
- Score (nominal)
- 4
- Publication indicators
- = 4.000; : 2014 = 0.678

- Uniform Resource Identifier
- https://researchportal.amu.edu.pl/info/article/UAM52e591b554b44587a4f8dcc3d9b8d77a/

* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perishopening in a new tab system.

Back