Nothing Special   »   [go: up one dir, main page]
Document Open Access Logo

Engineering Fast Algorithms for the Bottleneck Matching Problem

Authors Ioannis Panagiotas, Grégoire Pichon , Somesh Singh , Bora Uçar

PDF
Thumbnail PDF

File

LIPIcs.ESA.2023.87.pdf
  • Filesize: 0.86 MB
  • 15 pages

Document Identifiers

Author Details

Ioannis Panagiotas
  • Neo4j, Malmö, Sweden
Grégoire Pichon
  • Université Claude Bernard Lyon 1 and LIP, France
  • UMR5668, CNRS, ENS de Lyon, Inria, UCBL1, France
Somesh Singh
  • CNRS and LIP, ENS de Lyon, France
  • UMR5668, CNRS, ENS de Lyon, Inria, UCBL1, France
Bora Uçar
  • CNRS and LIP, ENS de Lyon, France
  • UMR5668, CNRS, ENS de Lyon, Inria, UCBL1, France

Cite As Get BibTex

Ioannis Panagiotas, Grégoire Pichon, Somesh Singh, and Bora Uçar. Engineering Fast Algorithms for the Bottleneck Matching Problem. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 87:1-87:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ESA.2023.87

Abstract

We investigate the maximum bottleneck matching problem in bipartite graphs. Given a bipartite graph with nonnegative edge weights, the problem is to find a maximum cardinality matching in which the minimum weight of an edge is the maximum. To the best of our knowledge, there are two widely used solvers for this problem based on two different approaches. There exists a third known approach in the literature, which seems inferior to those two which is presumably why there is no implementation of it. We take this third approach, make theoretical observations to improve its behavior, and implement the improved method. Experiments with the existing two solvers show that their run time can be too high to be useful in many interesting cases. Furthermore, their performance is not predictable, and slight perturbations of the input graph lead to considerable changes in the run time. On the other hand, the proposed solver’s performance is much more stable; it is almost always faster than or comparable to the two existing solvers, and its run time always remains low.

Subject Classification

ACM Subject Classification
  • Theory of computation
Keywords
  • bipartite graphs
  • assignment problem
  • matching

Metrics

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

Related Versions

Supplementary Materials

References

  1. M. Benzi and B. Uçar. Preconditioning techniques based on the Birkhoff-von Neumann decomposition. Computational Methods in Applied Mathematics, 17:201-215, 2017. Google Scholar
  2. G. Birkhoff. Tres observaciones sobre el algebra lineal. Univ. Nac. Tucumán Rev. Ser. A, 5:147-150, 1946. Google Scholar
  3. R. Burkard, M. Dell'Amico, and S. Martello. Assignment Problems. SIAM, Philadelphia, PA, USA, 2009. Google Scholar
  4. C. Chang, W. Chen, and H. Huang. On service guarantees for input-buffered crossbar switches: A capacity decomposition approach by Birkhoff and von Neumann. In Quality of Service, 1999. IWQoS '99. 1999 Seventh International Workshop on, pages 79-86, 1999. Google Scholar
  5. T. A. Davis and Y. Hu. The University of Florida sparse matrix collection. ACM Trans. Math. Softw., 38(1):1:1-1:25, 2011. Google Scholar
  6. 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
  7. I. S. Duff and J. Koster. The design and use of algorithms for permuting large entries to the diagonal of sparse matrices. SIAM Journal on Matrix Analysis and Applications, 20(4):889-901, 1999. Google Scholar
  8. I. S. Duff and J. Koster. On algorithms for permuting large entries to the diagonal of a sparse matrix. SIAM Journal on Matrix Analysis and Applications, 22:973-996, 2001. URL: https://doi.org/10.1137/S0895479899358443.
  9. F. Dufossé, K. Kaya, I. Panagiotas, and B. Uçar. Further notes on Birkhoff-von Neumann decomposition of doubly stochastic matrices. Linear Algebra and its Applications, 554:68-78, 2018. URL: https://doi.org/10.1016/j.laa.2018.05.017.
  10. F. Dufossé and B. Uçar. Notes on Birkhoff-von Neumann decomposition of doubly stochastic matrices. Linear Algebra and its Applications, 497:108-115, 2016. URL: https://doi.org/10.1016/j.laa.2016.02.023.
  11. A. L. Dulmage and N. S. Mendelsohn. Coverings of bipartite graphs. Canadian Journal of Mathematics, 10:517-534, 1958. Google Scholar
  12. H. N. Gabow and R. E. Tarjan. Algorithms for two bottleneck optimization problems. J. Algorithms, 9(3):411-417, 1988. Hopcroft-Karp algorithm can be used as an approximation algorithm p415. Google Scholar
  13. P. Hall. On representatives of subsets. Journal of the London Mathematical Society, s1-10(37):26-30, 1935. URL: http://jlms.oxfordjournals.org/cgi/reprint/s1-10/37/26.pdf.
  14. 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
  15. 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
  16. J. Kulkarni, E. Lee, and M. Singh. Minimum Birkhoff-von Neumann decomposition. In International Conference on Integer Programming and Combinatorial Optimization, pages 343-354. Springer, 2017. Google Scholar
  17. I. Panagiotas, G. Pichon, S. Singh, and B. Uçar. Bottled: Fast algorithms for the bottleneck matching problem, April 2023. URL: https://doi.org/10.5281/zenodo.7871464.
  18. A. Pothen and C.-J. Fan. Computing the block triangular form of a sparse matrix. ACM Transactions on Mathematical Software, 16(4):303-324, December 1990. URL: https://doi.org/10.1145/98267.98287.
  19. A. P. Punnen and K. Nair. Improved complexity bound for the maximum cardinality bottleneck bipartite matching problem. Discret. Appl. Math., 55(1):91-93, 1994. Google Scholar
  20. R. Sinkhorn and P. Knopp. Concerning nonnegative matrices and doubly stochastic matrices. Pacific J. Math., 21:343-348, 1967. Google Scholar
  21. V. Valls, G. Iosifidis, and L. Tassiulas. Birkhoff’s decomposition revisited: Sparse scheduling for high-speed circuit switches. IEEE/ACM Transactions on Networking, 29(6):2399-2412, 2021. URL: https://doi.org/10.1109/TNET.2021.3088327.
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