Document Open Access Logo

Engineering Fast Almost Optimal Algorithms for Bipartite Graph Matching

Authors Ioannis Panagiotas , Bora Uçar

PDF
Thumbnail PDF

File

LIPIcs.ESA.2020.76.pdf
  • Filesize: 0.73 MB
  • 23 pages

Document Identifiers

Author Details

Ioannis Panagiotas
  • ENS Lyon, France
Bora Uçar
  • CNRS and LIP, ENS Lyon, France

Cite As Get BibTex

Ioannis Panagiotas and Bora Uçar. Engineering Fast Almost Optimal Algorithms for Bipartite Graph Matching. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 76:1-76:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ESA.2020.76

Abstract

We consider the maximum cardinality matching problem in bipartite graphs. There are a number of exact, deterministic algorithms for this purpose, whose complexities are high in practice. There are randomized approaches for special classes of bipartite graphs. Random 2-out bipartite graphs, where each vertex chooses two neighbors at random from the other side, form one class for which there is an O(m+nlog n)-time Monte Carlo algorithm. Regular bipartite graphs, where all vertices have the same degree, form another class for which there is an expected O(m + nlog n)-time Las Vegas algorithm. We investigate these two algorithms and turn them into practical heuristics with randomization. Experimental results show that the heuristics are fast and obtain near optimal matchings. They are also more robust than the state of the art heuristics used in the cardinality matching algorithms, and are generally more useful as initialization routines.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • bipartite graphs
  • matching
  • randomized algorithm

Metrics

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

Supplementary Materials

References

  1. Z. Allen-Zhu, Y. Li, R. Mendes de Oliveira, and A. Wigderson. Much faster algorithms for matrix scaling. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pages 890-901, Berkeley, CA, USA, October 2017. Google Scholar
  2. J. Aronson, M. Dyer, A. Frieze, and S. Suen. Randomized greedy matching II. Random Structures & Algorithms, 6(1):55-73, 1995. Google Scholar
  3. S. Assadi, M. Bateni, A. Bernstein, V. Mirrokni, and C. Stein. Coresets meet edcs: algorithms for matching and vertex cover on massive graphs. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1616-1635. SIAM, 2019. Google Scholar
  4. S. Assadi and A. Bernstein. Towards a unified theory of sparsification for matching problems. arXiv preprint, 2018. URL: http://arxiv.org/abs/1811.02009.
  5. S. Behnezhad, S. Brandt, M. Derakhshan, M. Fischer, M. Hajiaghayi, R.M. Karp, and J. Uitto. Massively parallel computation of matching and mis in sparse graphs. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, pages 481-490, 2019. Google Scholar
  6. S. Behnezhad, J. Łącki, and V. Mirrokni. Fully dynamic matching: Beating 2-approximation in δ^ε update time. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2492-2508. SIAM, 2020. Google Scholar
  7. C. Berge. Two theorems in graph theory. Proceedings of the National Academy of Sciences of the USA, 43:842-844, 1957. Google Scholar
  8. A. Bernstein and C. Stein. Fully dynamic matching in bipartite graphs. In International Colloquium on Automata, Languages, and Programming, pages 167-179. Springer, 2015. Google Scholar
  9. B. Besser and M. Poloczek. Greedy matching: Guarantees and limitations. Algorithmica, 77(1):201-234, 2017. Google Scholar
  10. M. B. Cohen, A. Madry, D. Tsipras, and A. Vladu. Matrix scaling and balancing via box constrained newton’s method and interior point methods. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pages 902-913, Berkeley, CA, USA, October 2017. Google Scholar
  11. A. Czumaj, J. Łącki, A. Madry, S. Mitrovic, K. Onak, and P. Sankowski. Round compression for parallel matching algorithms. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 471-484. Association for Computing Machinery, 2018. Google Scholar
  12. T. A. Davis and Y. Hu. The University of Florida sparse matrix collection. ACM Transactions on Mathematical Software, 38(1):1:1-1:25, 2011. Google Scholar
  13. I. S. Duff. On algorithms for obtaining a maximum transversal. ACM Transactions on Mathematical Software, 7(3):315-330, 1981. Google Scholar
  14. I. S. Duff, K. Kaya, and B. Uçar. Design, implementation, and analysis of maximum transversal algorithms. ACM Transactions on Mathematical Software, 38:13:1-13:31, 2011. Google Scholar
  15. F. Dufossé, K. Kaya, I. Panagiotas, and B. Uçar. Approximation algorithms for maximum matchings in undirected graphs. In 2018 Proceedings of the Seventh SIAM Workshop on Combinatorial Scientific Computing, pages 56-65, 2018. Google Scholar
  16. F. Dufossé, K. Kaya, and B. Uçar. Two approximation algorithms for bipartite matching on multicore architectures. Journal of Parallel and Distributed Computing, 85:62-78, 2015. Google Scholar
  17. A. Frieze and T. Johansson. On random k-out subgraphs of large graphs. Random Structures & Algorithms, 50(2):143-157, 2017. Google Scholar
  18. A. Goel, M. Kapralov, and S. Khanna. Perfect matchings in O(nlog n) time in regular bipartite graphs. SIAM Journal on Computing, 42(3):1392-1404, 2013. Google Scholar
  19. A. V. Goldberg and R. E. Tarjan. A new approach to the maximum-flow problem. J. ACM, 35(4):921-940, 1988. Google Scholar
  20. T. Hagerup, K. Mehlhorn, and J. I. Munro. Maintaining discrete probability distributions optimally. In A. Lingas, R. Karlsson, and S. Carlsson, editors, 20th International Colloquium on Automata, Languages, and Programming (ICALP), pages 253-264, Berlin, Heidelberg, 1993. Springer Berlin Heidelberg. Google Scholar
  21. J. E. Hopcroft and R. M. Karp. An n^5/2 algorithm for maximum matchings in bipartite graphs. SIAM Journal on Computing, 2(4):225-231, 1973. Google Scholar
  22. R. M. Karp, A. H. G. Rinnooy Kan, and R. V. Vohra. Average case analysis of a heuristic for the assignment problem. Mathematics of Operations Research, 19(3):513-522, 1994. Google Scholar
  23. R. M. Karp and M. Sipser. Maximum matching in sparse random graphs. In 22nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 364-375, Los Alamitos, CA, USA, 1981. IEEE Computer Society. Google Scholar
  24. R. M. Karp, U. V. Vazirani, and V. V. Vazirani. An optimal algorithm for on-line bipartite matching. In Proceedings of the twenty-second annual ACM symposium on Theory of computing, STOC '90, pages 352-358, New York, NY, USA, 1990. ACM. Google Scholar
  25. K. Kaya, J. Langguth, F. Manne, and B. Uçar. Push-relabel based algorithms for the maximum transversal problem. Computers & Operations Research, 40(5):1266-1275, 2013. Google Scholar
  26. K. Kaya, J. Langguth, I. Panagiotas, and B. Uçar. Karp-Sipser based kernels for bipartite graph matching. In SIAM Symposium on Algorithm Engineering and Experiments (ALENEX), pages 134-145, Salt Lake City, Utah, US, January 2020. Google Scholar
  27. P. A. Knight. The Sinkhorn-Knopp algorithm: Convergence and applications. SIAM Journal on Matrix Analysis and Applications, 30(1):261-275, 2008. Google Scholar
  28. P. A. Knight and D. Ruiz. A fast algorithm for matrix balancing. IMA Journal of Numerical Analysis, 33(3):1029-1047, 2013. Google Scholar
  29. V. Korenwein, A. Nichterlein, R. Niedermeier, and P. Zschoche. Data reduction for maximum matching on real-world graphs: Theory and experiments. In 26th Annual European Symposium on Algorithms (ESA 2018), volume 112, pages 53:1-53:13, Dagstuhl, Germany, 2018. Google Scholar
  30. J. Langguth, F. Manne, and P. Sanders. Heuristic initialization for bipartite matching problems. Journal of Experimental Algorithmics (JEA), 15:1-22, 2010. Google Scholar
  31. J. Magun. Greedy matching algorithms, an experimental study. Journal of Experimental Algorithmics, 3:6, 1998. Google Scholar
  32. Y. Matias, J. S. Vitter, and W.-C. Ni. Dynamic generation of discrete random variates. Theory of Computing Systems, 36(4):329-358, 2003. Google Scholar
  33. N. McKeown. The iSLIP scheduling algorithm for input-queued switches. IEEE/ACM Transactions on Networking, 7:188-201, 1999. Google Scholar
  34. M. Mitzenmacher and E. Upfal. Probability and computing: Randomized algorithms and probabilistic analysis. Cambridge University Press, 1st edition, 2005. Google Scholar
  35. M. Poloczek and M. Szegedy. Randomized greedy algorithms for the maximum matching problem with new analysis. In Foundations of Computer Science (FOCS), 2012 IEEE 53rd Annual Symposium on, pages 708-717, 2012. Google Scholar
  36. A. Pothen and C.-J. Fan. Computing the block triangular form of a sparse matrix. ACM Transactions on Mathematical Software, 16(4):303-324, 1990. Google Scholar
  37. A. Pothen, S. M. Ferdous, and F. Manne. Approximation algorithms in combinatorial scientific computing. Acta Numerica, 28:541-633, 2019. Google Scholar
  38. R. Sinkhorn and P. Knopp. Concerning nonnegative matrices and doubly stochastic matrices. Pacific Journal of Mathematics, 21(2):343-348, 1967. Google Scholar
  39. G. Tinhofer. A probabilistic analysis of some greedy cardinality matching algorithms. Annals of Operations Research, 1(3):239-254, 1984. Google Scholar
  40. D. Walkup. Matchings in random regular bipartite digraphs. Discrete Mathematics, 31(1):59-64, 1980. 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