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

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

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.