Variants of matching:


There are several variants of the matching problem. The type of the graph introduces two main types of matching problems: bipartite and general. Although the asymptotic bounds are similar for these two classes of algorithms, there are significant differences in practice. The second major difference arises if the graph is weighted or not. In general, weighted matching is harder than the unweighted (maximum matching) variant of the problem. A further distinction arises if the weights are associated with the edges or with the vertices. While it is straight-forward to formulate the vertex-weighted matching problem as the edge-weighted by transferring the weights from vertices to edges, special algorithms for vertex-weighted matching are asymptotically better than their edge-weighted counterparts.

Another important distinction arises from the nature of the objective function: optimal versus approximate. In particular, approximation algorithms are important in the context of parallel implementations. Two other variants of matching that we have studied are semi-matching and b-matching.
 variants of matching

Our work:

Starting around 2004, our work on matching has spanned several aspects: a novel 2/3-rd approximation algorithm for bipartite vertex-weighted matching, novel approximation algorithms and their implementations on several multithreaded architectures, implementations on massively parallel processors, and novel applications of the matching problem in domain areas such as network alignment, fault tolerance and scheduling. Our work has also resulted in the development of several software libraries.

Serial implementations
  • Mahantesh Halappanavar
  • Florin Dobrian
  • Alex Pothen
 Software libraries:
  • Milan: A C++ library implementing several variants of the matching problem: bipartite maximum weighted matching, bipartite and general maximum (cardinality) matching, vertex-weighted matching, and approximation algorithms. The library was developed as part of the thesis by Mahantesh Halappanavar.
  • Matchbox: A C++ library implementing several variants of the matching problem in C++ developed by Florin Dobrian.

References:

  • Mahantesh Halappanavar. Algorithms for Vertex-Weighted Matching in Graphs. Ph.D. Dissertation. Old Dominion University, Norfolk, VA, USA. Advisor(s) Alex Pothen. 2009.
  • F Dobrian, M Halappanavar, and A Pothen. "A 2/3-Approximation Algorithm for Vertex Weighted Matching in Bipartite Graphs."(Journal submission under review). 2015.
Distributed-memory parallel implementations
  • Mahantesh Halappanavar
  • Florin Dobrian
  • Alex Pothen
 Software libraries:
  • Matchbox-P: Implementation of 1/2-approximate weighted matching in C++ and MPI targeted for massively parallel processors. Scalable performance has been demonstrated using up to 16,000 processors of IBM BlueGene/P.
References:
  • U Catalyurek, F Dobrian, A Gebremedhin, M Halappanavar, and A Pothen. "Distributed-memory Parallel Algorithms for Matching and Coloring." In proceedings of the PCO'11 New Trends in Parallel Computing and Optimization, in conjunction with IEEE IPDPS 2011, Anchorage, USA, May 16 -- 20, 2011.
Multithreaded implementations
  • Mahantesh Halappanavar
  • Alex Pothen
  • John Feo
  • Fredrik Manne
  • Ariful Azad
  • Johannes Langguth
  • Arif Khan
  • Md Naim
  • Oreste Villa
  • Antonino Tumeo
  • Erik Boman
  • Siva Rajamanickam
Software libraries:
  • Matchbox-MT: Implementation of 1/2-approximate algorithms targeting standard multi-core platforms and massively multithreaded Cray XMT platform. The code is developed and maintained by Mahantesh Halappanavar.
  • GPU-Suitor: 1/2-approximate weighted matching optimized for Nvidia Kepler K-40 platform. The code is developed by Md Naim. Further details are available here.
  • Maximum Matching: Implementation of maximum matching algorithms developed and maintained by Ariful Azad.
  • Maximum Matching: Implementation of maximum matching algorithms developed and maintained by Johannes Langguth.
  • Approximate Matching: Implementation of several approximate matching algorithms developed and maintained by Fredrik Manne.
References:
    M Halappanavar, Alex Pothen, Fredrik Manne, Ariful Azad, Johannes Langguth and Arif Khan. "Codesign Lessons Learned from Implementing Graph Matching Algorithms on Multithreaded Architectures." In IEEE Computer. Issue No 8. Volume 48. Pages 46--55. August 2015. DOI: 10.1109/MC.2015.215.
  • Fredrik Manne and Mahantesh Halappanavar. "New Effective Multithreaded Matching Algorithms." In proceedings of the IEEE 28th International Parallel and Distributed Processing Symposium, Phoenix, AZ, 19 -- 23 May, 2014.
  • J Langguth, A Azad, M Halappanavar, and F Manne. "On Parallel Push-Relabel Algorithms for Bipartite Maximum Matching." In Elsevier Journal of Parallel Computing: Systems and Applications (ParCo). Volume 40, Issue 7. Pages 289-308. July 2014. DOI: doi:10.1016/j.parco.2014.03.004.
  • M Halappanavar, J Feo, O Villa, A Tumeo, A Pothen. "Approximate Weighted Matching on Emerging Manycore and Multithreaded Architectures." In SAGE International Journal of High Performance Computing Applications (IJHPCA). Volume 26, No. 4. Pages 413--430. November, 2012. DOI: 10.1177/1094342012452893.
  • M Naim, F Manne, M Halappanavar, A Tumeo, J Langguth. "Optimizing Approximate Weighted Matching on Nvidia Kepler K40." In  proceedings of the 22nd annual IEEE International Conference on High Performance Computing (HiPC), Bengaluru, India, 16 -- 19 December, 2015.
  • A Azad, M Halappanavar, S Rajamanickam, E Boman, A Khan, and A Pothen. "Multithreaded Algorithms for Maximum Matching in Bipartite Graphs." In proceedings of the 26th IEEE International Parallel & Distributed Processing Symposium (IPDPS). Shanghai, China. May 20-24, 2012.
  • A Azad, M Halappanavar, F Dobrian, and A Pothen. "Computing Maximum Matching in Parallel on Bipartite Graphs: Worth the Effort?" In proceedings of the First Workshop on Irregular Applications: Architectures and Algorithm (IAAA '11). November, 2011.
  • A Khan, A Pothen, M Patwary, S Nadathur, N Sundaram, F Manne, M Halappanavar, and P Dubey. "Efficient Approximation Algorithms for Weighted B-Matching." (Journal submission under review).
Applications
  • Mahantesh Halappanavar
  • Alex Pothen
  • David Gleich
  • Arif Khan
  • Daniel Chavarría
  • S Krishnamoorthy
  • Nawab Ali
  • Luis de la Torre
 Software libraries:
  • NetAlign-MT: A C++ library implementing two methods for network alignment targeted for multicore platforms. The code is available from David Gleich's webpage.
  • Juggernaut: A C++ library implementing semi-matching and partial dustance-2 coloring for scheduling of judges. Further details are available here. A separate package is maintained by Ed Sowell.
  • Fault tolerant data distribution: A library for fault tolerant data distributions using C++ and MPI. The code is developed by Nawab Ali, Jeff Daily, Mahantesh Halappanavar and Sriram Krishnamoorthy.
  • Scheduling: A library for efficient scheduling in computational chemistry implemented by Daniel Chavarría. A separate library for energy-efficient assignment of tasks is developed by Luis de la Torre.
References:
  • A Khan, D Gleich, M Halappanavar, A Pothen. "A Multithreaded Algorithm for Network Alignment via Approximate Matching." In proceedings of the International Conference for High Performance Computing, Network, Storage and Analysis (SC'12). Salt Lake City, Utah. November 2012.
  • N Ali, S Krishnamoorthy, M Halappanavar, and J Daily. "Tolerating Correlated Failures for Generalized Cartesian Distributions via Bipartite Matching." In ACM International Conference on Computing Frontiers, Ischia, Italy 2011.
  • D Chavarría-Miranda, M Halappanavar, S Krishnamoorthy, JB Manzano Franco, A Vishnu, and A Hoisie. "On the Impact of Execution Models: A Case Study in Computational Chemistry." In proceedings of the Workshop on Large-Scale Parallel Processing (LSPP) to be held in conjunction with the IEEE 29th International Parallel and Distributed Processing Symposium (IPDPS), Hyderabad, India, 25 -- 29 May, 2015.
  • M Halappanavar, M Schram, L de la Torre, K Barker, N Tallent, and D Kerbyson. "Towards Efficient Scheduling of Data Intensive High Energy Physics Workflows." In proceedings of the WORKS 2015 Workshop, held in conjunction with the International Conference for High Performance Computing, Networking, Storage and Analysis (SC15).
  • Match. Color. Repeat: Combinatorial graph techniques put schedulers in the driver's seat. A promotional article written on this topic. A PDF copy of the article made accessible from this website.


Last updated:
Access stats