matching and scaling

A project on graph and hypergraph matching and matrix scaling.

Bipartite graph matching is one of the fundamental problems in graph theory and combinatorial optimization. The problem asks for a maximum set of vertex disjoint edges in a given bipartite graph. It has many applications in a variety of fields such as image processing, chemical structure analysis, and bioinformatics. Our motivating application lies in solving sparse linear systems of equations, as algorithms for computing a maximum cardinality bipartite matching are run routinely in the related solvers. In this setting, bipartite matching algorithms are used to see if the associated coefficient matrix is reducible; if so, substantial savings in computational requirements can be achieved. In this project, we analyze the efficiency of the exact and probabilistic matching algorithms. The problem is also related with matrix permanents, matrix scaling algorithms. Furthermore, we have also investigated matching on hypergraphs which is also a popular problem in the literature.

Related Publications:

  • Scaling matrices and counting the perfect matchings in graphs. Fanny Dufossé, Kamer Kaya, Ioannis Panagiotas, Bora Uçar, Discrete Applied Mathematics, 2020
  • Karp-Sipser based kernels for bipartite graph matching. Kamer Kaya, Johannes Langguth, Ioannis Panagiotas, Bora Uçar. Proceedings of the Twenty-Second Workshop on Algorithm Engineering and Experiments (ALENEX), 134-145, 2020
  • Effective heuristics for matchings in hypergraphs. Fanny Dufossé, Kamer Kaya, Ioannis Panagiotas, Bora Uçar. International Symposium on Experimental Algorithms, 248-264, 2019
  • Further notes on Birkhoff–von Neumann decomposition of doubly stochastic matrices. Fanny Dufossé, Kamer Kaya, Ioannis Panagiotas, Bora Uçar. Linear Algebra and its Applications, 554, 68-78, 2018
  • Approximation algorithms for maximum matchings in undirected graphs. Fanny Dufossé, Kamer Kaya, Ioannis Panagiotas, Bora Uçar. Proceedings of the Seventh SIAM Workshop on Combinatorial Scientific Computing, 56-65, 2018
  • Two approximation algorithms for bipartite matching on multicore architectures. Fanny Dufossé, Kamer Kaya, Bora Uçar, Journal of Parallel and Distributed Computing, 85, 62-78, 2016
  • Bipartite matching heuristics with quality guarantees on shared memory parallel computers. Fanny Dufossé, Kamer Kaya, Bora Uçar. IEEE 28th International Parallel and Distributed Processing Symposium, 540-549, 2014
  • A push-relabel-based maximum cardinality bipartite matching algorithm on GPUs. Mehmet Deveci, Kamer Kaya, Bora Uçar, Ümit V Çatalyürek. 42nd International Conference on Parallel Processing, 21-29, 2013
  • GPU accelerated maximum cardinality matching algorithms for bipartite graphs. Mehmet Deveci, Kamer Kaya, Bora Uçar, Ümit V Catalyürek, European Conference on Parallel Processing, 850-861, 2013
  • Push-relabel based algorithms for the maximum transversal problem. Kamer Kaya, Johannes Langguth, Fredrik Manne, Bora Uçar. Computers & Operations Research, 40, 5, 1266-1275, 2013
  • On shared-memory parallelization of a sparse matrix scaling algorithm. Ümit V Çatalyürek, Kamer Kaya, Bora Uçar. 41st International Conference on Parallel Processing, 68-77, 2012
  • Design, Implementation, and Analysis of Maximum Transversal Algorithms. IS Duff, K Kaya, B Uçar. ACM Transactions on Mathematical Software-TOMS, 38, 2, 2012