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

每年从美国医学院毕业的19,000名学生都会与他们将接受住院医师培训的医院相匹配。学生和医院都会对他们的选择进行排名，并使用一种算法来寻找匹配，为每个学生提供他们最好的可用选择。这些问题还出现在其他情况下：将器官捐赠者匹配到其身体不会排斥移植器官的接受者，根据他们的兴趣将广告匹配给网民等等。各种匹配问题和相关的边缘覆盖问题在称为图的组合对象上在计算机科学中形式化，涉及美丽的数学、复杂的算法、这些算法在现代台式计算机和超级计算机上的有效实施，以及对计算科学和工程、数据科学、网络科学等应用领域中出现的一些问题的经验评估。在这个项目中，两个PI将开发用于匹配和边缘覆盖问题的新算法和软件。并为科学、工程和工业各个领域的从业者提供实现。PIS还将在这个项目中培训两名博士生，并开发教学资源，使计算机科学本科生和研究生能够接触到这些发展。几十年来，在许多备受瞩目的工业和医疗应用的推动下，计算最大化某个目标函数的匹配问题一直被积极研究。本课题致力于满足现代应用需求的匹配算法的设计、理论分析和实现，并考虑了b-匹配、b-边覆盖、度量匹配等广义匹配问题。精确计算最佳匹配的经典串行算法并不总是适用于可能包含数十亿条边的海量图形数据集。幸运的是，在许多应用中，拥有近乎最佳的匹配就足够了，而不是精确的最佳匹配。这个项目的一个目标是设计简单高效的匹配算法，并且得到可证明的良好的近似解。本项目将研究几个关于广义加权匹配问题的可逼近性的公开问题，特别是在匹配类型的问题上允许线性时间算法的逼近因子任意接近于1的情况下。为此，PI将研究放宽广义加权匹配问题的标准线性规划公式如何允许更有效的算法。这些算法和其他算法将被修改，以使它们在支持并行计算的现代处理器上高效。两名博士生将在这个项目中接受培训。广义图匹配算法现在被应用于数值线性代数软件中，用于预处理、图聚类、数据匿名化和网络比对。PI将评估新的和现有的算法在这些应用程序上的性能。PI将免费提供在该项目下开发的所有匹配算法代码。20世纪中期的基本匹配算法牢固地建立在计算机科学教育的典范中，但很少有现代匹配算法在本科生水平上被教授。PIS将把现代匹配和应用模块纳入他们在普渡大学和密歇根大学的课程中，并将这些材料公开提供。

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.