BPCPPDYSOE21 – wissenschaftliches Programm
Bereiche | Tage | Auswahl | Suche | Aktualisierungen | Downloads | Hilfe
SOE: Fachverband Physik sozio-ökonomischer Systeme
SOE 3: Poster
SOE 3.5: Poster
Montag, 22. März 2021, 17:30–19:30, SOEp
Numerical study of phase transition in the bipartite z-matching — •Till Kahlke1, Martin Fränzle2, and Alexander K. Hartmann1 — 1Institut of Physics, University of Oldenburg, Germany — 2Institut of Computer Science, University of Oldenburg, Germany
We study numerically [1] the many-to-one bipartite z-matching, a generalisation of the matching problem. It can be used, e.g., to model a wireless communication network of users and servers, where z denotes the maximum number of users a server can treat at one time. Within a bipartite graph representation, there are links from each user to all servers which are feasible, e.g., close enough. The maximum matching capacity of this graph is the largest total number of users all servers can serve. After mapping to standard maximum matching, we use a numerically exact algorithm (Edmonds blossom shrinking) to solve the z-matching problem. First, we compare it with previous analytic results [2]. Next, we look at the saturation probability as order parameter and observe phase transitions when varying the average number of neighbors. We describe these transitions by their critical points and an universal critical exponent. When comparing the matchings of the exact algorithm with a commonly used matching heuristic, we observe that the heuristic starts to differ from the optimal solution right at the critical point.
[1] A.K. Hartmann, Big Practical Guide to Computer Simulations (World Scientific, 2015).
[2] E. Kreačić and G. Bianconi, Europhys. Lett. 126, 28001 (2019).