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

AitF：协作研究：弥合匹配和边缘覆盖问题理论与实践之间的差距

• 批准号: 1637534
• 负责人: Alex Pothen
• 金额: $ 39.94万
• 依托单位: Purdue University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-09-01 至 2021-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1637534&HistoricalAwards=false
• 关键词: AitF; Collaborative; Research; Bridging; Gap

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.

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

项目成果

A Parallel Approximation Algorithm for Maximizing Submodular b-Matching

最大化子模b匹配的并行逼近算法

• DOI: 10.1137/1.9781611976830.5
• 发表时间: 2021
• 期刊: Proceedings of the 2021 SIAM Conference on Applied and Computational Discrete Algorithms (ACDA21
• 作者: Ferdous, S;Pothen, A;Khan, A.;Panyala, A.;Halappanavar, M.
• 通讯作者: Halappanavar, M.

Edge pushing is equivalent to vertex elimination for computing Hessians

推边相当于计算 Hessians 的顶点消除

• DOI: 10.1137/1.9781611974690.ch11
• 发表时间: 2016
• 期刊: Proceedings of SIAM Workshop on Combinatorial Scientific Computing
• 作者: Mu Wang, Alex Pothen

Fast Parallel Stochastic Subspace Algorithms for Large-Scale Ambient Oscillation Monitoring

• DOI: 10.1109/tsg.2016.2608965
• 发表时间: 2017-05-01
• 期刊: IEEE TRANSACTIONS ON SMART GRID
• 影响因子: 9.6
• 作者: Wu, Tianying;Venkatasubramanian, Vaithianathan (Mani);Pothen, Alex
• 通讯作者: Pothen, Alex

A New 3/2-Approximation Algorithm for the b-Edge Cover Problem

• DOI: 10.1137/1.9781611974690.ch6
• 发表时间: 2016
• 作者: Arif M. Khan;A. Pothen

A 2/3-Approximation Algorithm for Vertex Weighted Matching in Bipartite Graphs

二分图中顶点加权匹配的2/3近似算法

• DOI: 10.1137/17m1140029
• 发表时间: 2019
• 期刊: SIAM Journal on Scientific Computing
• 影响因子: 3.1
• 作者: Dobrian, Florin;Halappanavar, Mahantesh;Pothen, Alex;Al-Herz, Ahmed
• 通讯作者: Al-Herz, Ahmed