AitF:Collaborative Research: Bridging the Gap between Theory and Practice for Matching and Edge Cover Problems

Purdue University, West Lafayette IN

Investigators

Abstract

Every year the 19,000 students who graduate from medical schools in the U.S. are matched with the hospitals where they will do their residency training. Both students and hospitals rank their choices, and an algorithm is used to find a matching that gives each student their best available choice. These problems also arise in other contexts: matching organ donors to recipients whose bodies will not reject the transplanted organ, matching advertisements to web surfers based on their interests, etc. Variations of matching problems, and related edge cover problems, are formalized in computer science on combinatorial objects called graphs, and involve beautiful mathematics, sophisticated algorithms, efficient implementations of these algorithms on modern desk-top computers and supercomputers, and empirical evaluation on a number of problems that arise in application areas such as computational science and engineering, data science, network science, etc. In this project, the two PIs will develop new algorithms and software for matching and edge cover problems, and make implementations available for practitioners in various fields of science, engineering and industry. The PIs will also train two PhD students in this project, and develop teaching resources to make these developments accessible to undergraduate and graduate students in computer science. The problem of computing a matching that maximizes some objective function has been actively investigated for decades, driven by many high-profile industrial and medical applications. This project focuses on the design, theoretical analysis, and implementation of matching algorithms that meet the needs of modern applications, and considers generalized matching problems such as b-matching, b-edge cover, and metric matching. Classical serial algorithms that compute exactly optimum matchings are not always suited to massive graph data sets, which can contain billions of edges. Fortunately, in many applications it suffices to have nearly optimum matchings rather than exactly optimum ones. One goal of this project is to design simple and efficient matching algorithms that are both highly parallel, and produce provably good approximate solutions. This project will examine several open problems on the approximability of generalized weighted matching problems, particularly on which matching-type problems admit linear time algorithms with approximation factor arbitrarily close to one. To that end, the PIs will study how relaxing standard linear programming formulations of generalized weighted matching problems allows for more efficient algorithms. These and other algorithms will be modified to make them efficient on modern processors that support parallel computing. Two PhD students will be trained in this project. Generalized graph matching algorithms are now applied in numerical linear algebra software, for preconditioning, graph clustering, anonymizing data, and network alignment. The PIs will evaluate the performance of new and existing algorithms on these applications. The PIs will make freely available all code of matching algorithms developed under this project. Basic matching algorithms from the mid-20th century are firmly established in the canon of computer science education, but few modern matching algorithms are taught at the undergraduate level. The PIs will incorporate modules on modern matching and applications into their courses at Purdue University and the University of Michigan, and make these materials publicly available.