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

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

基本信息

批准号：
1637546
负责人：
Seth Pettie
金额：
$ 40万
依托单位：
Regents of the University of Michigan - Ann Arbor
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2016
资助国家：
美国
起止时间：
2016-09-01 至 2021-08-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1637546&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边缘封面和度量匹配等广义匹配问题。准确计算最佳匹配的经典串行算法并不总是适合大量的图形数据集，其中可能包含数十亿个边缘。幸运的是，在许多应用中，几乎具有最佳匹配而不是最佳匹配功能就足够了。该项目的一个目标是设计简单有效的匹配算法，这些算法高度平行，并且可证明是良好的近似解决方案。本项目将研究一些关于广义加权匹配问题的近似性的开放性问题近似因子任意接近一个的线性时间算法。为此，PI将研究一般加权匹配问题的放松标准线性编程公式如何产生更有效的算法。这些算法和其他算法将被修改，以使它们在支持并行计算的现代处理器上有效。将在该项目中对两名博士学位学生进行培训。现在，使用数值线性代数软件中应用广义图匹配算法，用于预处理，图形群集，匿名数据和网络对齐。 PI将评估这些应用程序上新算法和现有算法的性能。 PI将免费提供所有在该项目下制定的匹配算法的守则。在计算机科学教育的规范中，牢固地确定了20世纪中叶的基础匹配算法，但是很少有现代匹配算法在本科生层面教授。 PIS将在普渡大学和密歇根大学的课程中纳入现代匹配和应用的模块，并将这些材料公开提供。

项目成果

期刊论文数量（51）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

The Complexity of (Δ+1) Coloring in Congested Clique, Massively Parallel Computation, and Centralized Local Computation

DOI：
10.1145/3293611.3331607
发表时间：
2019-01-01
期刊：
PROCEEDINGS OF THE 2019 ACM SYMPOSIUM ON PRINCIPLES OF DISTRIBUTED COMPUTING (PODC '19)
影响因子：
0
作者：
Chang, Yi-Jun;Fischer, Manuela;Zheng, Yufan
通讯作者：
Zheng, Yufan

Near-optimal Distributed Triangle Enumeration via Expander Decompositions

通过扩展器分解进行近乎最优的分布式三角形枚举