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

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