Document Open Access Logo

Improved Deterministic Distributed Matching via Rounding

Author Manuela Fischer

PDF
Thumbnail PDF

File

LIPIcs.DISC.2017.17.pdf
  • Filesize: 0.53 MB
  • 15 pages

Document Identifiers

Author Details

Manuela Fischer

Cite As Get BibTex

Manuela Fischer. Improved Deterministic Distributed Matching via Rounding. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 17:1-17:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.DISC.2017.17

Abstract

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.

Subject Classification

Keywords
  • distributed graph algorithms
  • deterministic distributed algorithms
  • rounding linear programs
  • maximal matching
  • maximum matching approximation

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Noga Alon, László Babai, and Alon Itai. A fast and simple randomized parallel algorithm for the maximal independent set problem. Journal of algorithms, 7(4):567-583, 1986. Google Scholar
  2. Noga Alon, Ronitt Rubinfeld, Shai Vardi, and Ning Xie. Space-efficient local computation algorithms. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1132-1139, 2012. Google Scholar
  3. Leonid Barenboim, Michael Elkin, Seth Pettie, and Johannes Schneider. The locality of distributed symmetry breaking. In Proceedings of the Symposium on Foundations of Computer Science (FOCS), pages 321-330, 2012. Google Scholar
  4. Yi-Jun Chang, Tsvi Kopelowitz, and Seth Pettie. An exponential separation between randomized and deterministic complexity in the LOCAL model. In Proceedings of the Symposium on Foundations of Computer Science (FOCS), pages 615-624, 2016. Google Scholar
  5. Andrzej Czygrinow and Michał Hańćkowiak. Distributed algorithm for better approximation of the maximum matching. In International Computing and Combinatorics Conference, pages 242-251, 2003. Google Scholar
  6. Andrzej Czygrinow, Michał Hańćkowiak, and Edyta Szymańska. Distributed algorithm for approximating the maximum matching. Discrete Applied Mathematics, 143(1):62-71, 2004. Google Scholar
  7. Andrzej Czygrinow, Michał Hańćkowiak, and Edyta Szymańska. A fast distributed algorithm for approximating the maximum matching. In Proceedings of the Annual European Symposium on Algorithms (ESA), volume 3221, pages 252-263, 2004. Google Scholar
  8. Guy Even, Moti Medina, and Dana Ron. Deterministic stateless centralized local algorithms for bounded degree graphs. In Proceedings of the Annual European Symposium on Algorithms (ESA), pages 394-405, 2014. Google Scholar
  9. Manuela Fischer. Improved deterministic distributed matching via rounding. CoRR, abs/1703.00900, 2017. URL: http://arxiv.org/abs/1703.00900.
  10. Mohsen Ghaffari. An improved distributed algorithm for maximal independent set. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 270-277, 2016. Google Scholar
  11. Mohsen Ghaffari, Fabian Kuhn, and Yannic Maus. On the complexity of local distributed graph problems. In Proceedings of the Symposium on Theory of Computing (STOC), pages 784-797, 2017. Google Scholar
  12. Mohsen Ghaffari and Hsin-Hao Su. Distributed degree splitting, edge coloring, and orientations. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2505-2523, 2017. Google Scholar
  13. Mika Göös, Juho Hirvonen, and Jukka Suomela. Linear-in-delta lower bounds in the local model. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 86-95, 2014. Google Scholar
  14. Michał Hańćkowiak, Michał Karonski, and Alessandro Panconesi. On the distributed complexity of computing maximal matchings. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 219-225, 1998. Google Scholar
  15. Michał Hańćkowiak, Michał Karonski, and Alessandro Panconesi. On the distributed complexity of computing maximal matchings. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 219-225, 1998. Google Scholar
  16. Michał Hańćkowiak, Michał Karoński, and Alessandro Panconesi. A faster distributed algorithm for computing maximal matchings deterministically. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 219-228, 1999. Google Scholar
  17. David G. Harris, Johannes Schneider, and Hsin-Hao Su. Distributed (Δ+ 1)-coloring in sublogarithmic rounds. In Proceedings of the Symposium on Theory of Computing (STOC), pages 465-478, 2016. Google Scholar
  18. Juho Hirvonen and Jukka Suomela. Distributed maximal matching: Greedy is optimal. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 165-174, 2012. Google Scholar
  19. Amos Israeli and Alon Itai. A fast and simple randomized parallel algorithm for maximal matching. Information Processing Letters, 22(2):77-80, 1986. Google Scholar
  20. Amos Israeli and Yossi Shiloach. An improved parallel algorithm for maximal matching. Information Processing Letters, 22(2):57-60, 1986. Google Scholar
  21. Christos Koufogiannakis and Neal E. Young. Distributed fractional packing and maximum weighted b-matching via tail-recursive duality. In Proceedings of the International Symposium on Distributed Computing (DISC), pages 221-238, 2009. Google Scholar
  22. Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer. The price of being near-sighted. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 980-989, 2006. Google Scholar
  23. Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer. Local computation: Lower and upper bounds. J. ACM, 63(2):17:1-17:44, 2016. Google Scholar
  24. Nathan Linial. Distributive graph algorithms - global solutions from local data. In Proceedings of the Symposium on Foundations of Computer Science (FOCS), pages 331-335, 1987. Google Scholar
  25. Nathan Linial. Locality in distributed graph algorithms. SIAM Journal on Computing, 21(1):193-201, 1992. Google Scholar
  26. Zvi Lotker, Boaz Patt-Shamir, and Seth Pettie. Improved distributed approximate matching. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 129-136, 2008. Google Scholar
  27. Zvi Lotker, Boaz Patt-Shamir, and Adi Rosen. Distributed approximate matching. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 167-174, 2007. Google Scholar
  28. Michael Luby. A simple parallel algorithm for the maximal independent set problem. SIAM journal on computing, 15(4):1036-1053, 1986. Google Scholar
  29. Henry Martyn Mulder. Julius petersen’s theory of regular graphs. Discrete mathematics, 100(1-3):157-175, 1992. Google Scholar
  30. Alessandro Panconesi and Romeo Rizzi. Some simple distributed algorithms for sparse networks. Distributed computing, 14(2):97-100, 2001. Google Scholar
  31. Alessandro Panconesi and Mauro Sozio. Fast primal-dual distributed algorithms for scheduling and matching problems. Distributed Computing, 22(4):269-283, 2010. Google Scholar
  32. Michal Parnas and Dana Ron. Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms. Theoretical Computer Science, 381(1):183-196, 2007. Google Scholar
  33. Ronitt Rubinfeld, Gil Tamir, Shai Vardi, and Ning Xie. Fast local computation algorithms. In Proceedings of the Symposium on Innovations in Computer Science (ICS), pages 223-238, 2011. Google Scholar
  34. Jukka Suomela. Distributed algorithms for edge dominating sets. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 365-374, 2010. Google Scholar
  35. Mirjam Wattenhofer and Roger Wattenhofer. Distributed weighted matching. In Proceedings of the International Symposium on Distributed Computing (DISC), pages 335-348, 2004. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact