EAGER: Approximation Algorithms for b-Matching and b-Edge Covers

EAGER：b 匹配和 b 边缘覆盖的近似算法

• 批准号: 1552323
• 负责人: Alex Pothen
• 金额: $ 9.9万
• 依托单位: Purdue University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-09-01 至 2016-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1552323&HistoricalAwards=false
• 关键词: EAGER; Approximation; Algorithms; Matching; Edge

Here is a puzzle: a group of people is told to each shake the hand of someone they like; how can they quickly have many simultaneous handshakes? And what if some can use both hands, others are chimps that can use their feet, or even octopi that can shake with 8 others? This silly puzzle (b-Matching) has a serious purpose, since this type of decision is often faced in computer systems where entities can interact or communicate with a limited number of other entities, and they need to negotiate quickly to maximize interaction. A related puzzle (b-Edge cover), of having every hand holding another, arises in the data privacy concept of b-Anonymity. In this project, the PI will work with a PhD student to design and implement fast approximation algorithms for b-Matchings and b-Edge Covers, and apply them k-Anonymity. A b-Matching M is a set of edges in a weighted graph such that at most b(v) edges in M are incident on each vertex v; the weight of a b-Matching is the sum of the weights of the matched edges. This project aims to design a fast approximation algorithm that achieves at least half the weight of the maximum weighted matching. A b-Edge Cover is a subset of edges C such that at least b(v) edges in C are incident on each vertex v in the graph; this project aims to design a 3/2-approximation algorithm for the b-Edge Cover problem. These algorithms will be implemented on multicore architectures that support multiple threads of concurrency. The impact of the algorithms in application areas such as data privacy (k-Anonymity) and preconditioning will be evaluated. To ensure broad applicability, the PI and PhD student will work also with collaborators from industry and national laboratories, and will produce modules for a graduate course in advanced graph algorithms. The PI will also present matching algorithms applied to the medical resident matching problem to students at the West Lafayette Jr/Sr High School and Harrison High School with the assistance of the Purdue Computer Science department's K-12 outreach program.

这里有一个难题：一组人被告知每个人都要和他们喜欢的人握手，他们怎么能很快地同时握手呢？ 如果有些猩猩能用双手，有些猩猩能用脚，甚至章鱼能和其他8只猩猩握手，那会怎么样呢？ 这个愚蠢的难题（b-匹配）有一个严肃的目的，因为这种类型的决策通常在计算机系统中面临，其中实体可以与有限数量的其他实体进行交互或通信，并且它们需要快速协商以最大化交互。一个相关的难题（b-Edge cover），即每只手都握着另一只手，出现在b-Anciliity的数据隐私概念中。在这个项目中，PI将与一名博士生合作，设计和实现b-匹配和b-边覆盖的快速近似算法，并将其应用于k-匹配。b-匹配M是加权图中的一组边，使得M中最多B（v）条边入射到每个顶点v上; b-匹配的权重是匹配边的权重之和。本计画的目标是设计一个快速的近似演算法，以达到最大加权匹配的一半权重。b-边覆盖是边C的子集，使得C中至少有B（v）条边与图中的每个顶点v关联;本项目旨在为b-边覆盖问题设计一个3/2近似算法。这些算法将在支持多线程并发的多核架构上实现。将评估算法在数据隐私（k-匿名性）和预处理等应用领域的影响。为了确保广泛的适用性，PI和博士生还将与来自行业和国家实验室的合作者合作，并将为高级图形算法的研究生课程制作模块。PI还将在普渡大学计算机科学系K-12外展计划的协助下，向西拉斐特小/老高中和哈里森高中的学生介绍应用于医疗住院医师匹配问题的匹配算法。