2026-07-22T12:34:44Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8002 2024-03-06T10:41:39Z ddc:004 open_access

Improved Deterministic Distributed Matching via Rounding Fischer, Manuela distributed graph algorithms deterministic distributed algorithms rounding linear programs maximal matching maximum matching approximation We present improved deterministic distributed algorithms for a number of well-studied matching problems, which are simpler, faster, more accurate, and/or more general than their known counterparts. The common denominator of these results is a deterministic distributed rounding method for certain linear programs, which is the first such rounding method, to our knowledge. A sampling of our end results is as follows. - An O(log^2 Delta log n)-round deterministic distributed algorithm for computing a maximal matching, in n-node graphs with maximum degree Delta. This is the first improvement in about 20 years over the celebrated O(log^4 n)-round algorithm of Hanckowiak, Karonski, and Panconesi [SODA'98, PODC'99]. - A deterministic distributed algorithm for computing a (2+epsilon)-approximation of maximum matching in O(log^2 Delta log(1/epsilon) + log^* n) rounds. This is exponentially faster than the classic O(Delta + log^* n)-round 2-approximation of Panconesi and Rizzi [DIST'01]. With some modifications, the algorithm can also find an epsilon-maximal matching which leaves only an epsilon-fraction of the edges on unmatched nodes. - An O(log^2 Delta log(1/epsilon) + log^* n)-round deterministic distributed algorithm for computing a (2+epsilon)-approximation of a maximum weighted matching, and also for the more general problem of maximum weighted b-matching. These improve over the O(log^4 n log_(1+epsilon) W)-round (6+epsilon)-approximation algorithm of Panconesi and Sozio [DIST'10], where W denotes the maximum normalized weight. - A deterministic local computation algorithm for a (2+epsilon)-approximation of maximum matching with 2^O(log^2 Delta) log^* n queries. This improves almost exponentially over the previous deterministic constant approximations which have query-complexity of 2^Omega(Delta log Delta) log^* n. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Manuela Fischer 2017 Is Part Of LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2017.17 urn:nbn:de:0030-drops-80027 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.17 eng https://creativecommons.org/licenses/by/3.0/legalcode