Tutte Colloquium - Alex Pothen

Title: Approximation Algorithms for Matchings in Big Graphs

Abstract:

Matchings in graphs are classical problems in combinatorial optimization and computer science, significant due to their theoretical importance and relevance to applications. Polynomial time algorithms for several variant matching problems with linear objective functions have been known for fifty years, with important contributions from Tutte, Edmonds, Cunningham, and Pulleyblank (all with Waterloo associations), and they are discussed in the textbook literature. However, these sophisticated polynomial time algorithms could fail to compute matching in big graphs with billions of edges. They are also not concurrent and thus practical parallel algorithms are not known.

This has led to work in the last twenty years on designing approximation algorithms for variant matching problems with near-linear time complexity in the size of the graphs. Approximation has become a useful paradigm for designing parallel matching algorithms. In this talk I will report on fast approximation algorithms for three problems: maximum vertex-weighted matchings, maximum edge-weighted matchings and b-matchings, and maximum edge-weighted b-matchings with submodular objective functions (this latter problem is NP-hard). For each problem, we will describe the combinatorial structure in the problem that leads to fast approximations. We will also mention the design of parallel algorithms, and applications to internet advertising, quantum chemistry, and data privacy.