@inproceedings{eee8e31559394d22a12d08d84cef89cc,
title = "Distributed Approximations of f-Matchings and b-Matchings in Graphs of Sub-Logarithmic Expansion",
abstract = "We give a distributed algorithm which given ϵ > 0 finds a (1 - ϵ)-factor approximation of a maximum f-matching in graphs G = (V, E) of sub-logarithmic expansion. Using a similar approach we also give a distributed approximation of a maximum b-matching in the same class of graphs provided the function b : V → Z+ is L-Lipschitz for some constant L. Both algorithms run in O(log∗ n) rounds in the LOCAL model, which is optimal.",
keywords = "B-matching, Distributed algorithms, F-matching",
author = "Andrzej Czygrinow and Micha{\l} Han{\'c}kowiak and Marcin Witkowski",
note = "Funding Information: Research supported in part by Simons Foundation Grant # 521777. Publisher Copyright: {\textcopyright} Andrzej Czygrinow, Micha{\l}Han{\'c}kowiak, and Marcin Witkowski.; 32nd International Symposium on Algorithms and Computation, ISAAC 2021 ; Conference date: 06-12-2021 Through 08-12-2021",
year = "2021",
month = dec,
day = "1",
doi = "10.4230/LIPIcs.ISAAC.2021.59",
language = "English (US)",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Hee-Kap Ahn and Kunihiko Sadakane",
booktitle = "32nd International Symposium on Algorithms and Computation, ISAAC 2021",
}