Advanced Computing, Mathematics and Data
Staff Awards & Honors
January 2017
Halappanavar Caps Inaugural SIAM Conference with Best Paper Award
CSC16 papers recently published as part of SIAM proceedings series
Congratulations to Mahantesh Halappanavar, the Analytics and Algorithms Team Lead with ACMD Division’s Data Sciences group, who co-authored “On Stable Marriages and Greedy Matchings,” which earned the Best Paper award as part of the inaugural peer-reviewed proceedings at the Society for Industrial and Applied Mathematics (SIAM) Workshop on Combinatorial Scientific Computing, or CSC16, held last October in in Albuquerque, New Mexico. This first-ever CSC best paper, which Halappanavar co-authored with Fredrik Manne, Md. Naim, and Haakon Lerring, all from the University of Bergen (Norway), Department of Informatics, recently was published by SIAM as part of its conference proceedings series.
Award excerpt: “…for the way the paper brings together several decades of work on stable marriages with the more recent work on approximation algorithms for weighted matchings, and the consequences for the average case complexity of the latter algorithms.” Enlarge Image.
According to SIAM News, CSC16 featured “leading researchers from around the world interested in the interaction of combinatorial (discrete) mathematics and algorithms with computational science and engineering.” Halappanavar and his co-authors’ award-winning paper examined the mathematics surrounding the classical stable marriage problem and recent greedy matching algorithms and their unexpected connection.
The stable marriage problem has resulted in algorithms with applications in varied real-world scenarios, including assigning new doctors to hospitals, students to schools, and human organs to transplant recipients. It even led to the 2012 Nobel Prize in Economics awarded to Lloyd S. Shapley and Alvin E. Roth. Meanwhile, greedy matching problems have yielded code for combinatorial scientific applications that can be implemented on various high-performance computer architectures to generate fast scalable algorithms.
Notably, in their work, Halappanavar and his colleagues showed that several algorithms for computing greedy matchings represent special cases of classical algorithms for stable marriage problems. This connection of the usually theoretical stable marriage problem with practical greedy matching enabled the creation of parallel algorithms for the stable marriage problem, indicating that much of the work done on greedy matchings can carry over to developing efficient code for stable marriage problems.
Dr. Mahantesh Halappanavar
“This work helped generate the first efficient graphics processing unit algorithm for the stable marriage problem,” Halappanavar explained. “While the main concepts behind the problem were developed in the 1950s and 60s using the idea of matching 10 couples into ‘stable’ marriages, where none break up because staying together is the optimum result, there still are many ways this classical problem can be applied to improve modern combinatorial scientific applications. We also are afforded more insights into how greedy matching algorithm behavior affects how we implement practical scalable solutions on modern computing hardware.”
Reference:
Manne F, M Naim, H Lerring, and M Halappanavar. 2016. “On Stable Marriages and Greedy Matchings.” In 2016 Proceedings of the Seventh SIAM Workshop on Combinatorial Scientific Computing, eds. AH Gebremedhin, EG Boman, and B Ucar, pp. 92-101. October 10-12, 2016, Albuquerque, New Mexico. SIAM, Philadelphia, Pennsylvania. DOI: 10.1137/1.9781611974690.
Related:
