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

Purdue University, West Lafayette IN

Investigators

Abstract

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.