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

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

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.