Contact Info
Combinatorics & Optimization
University of Waterloo
Waterloo, Ontario
Canada N2L 3G1
Phone: 519-888-4567, ext 33038
PDF files require Adobe Acrobat Reader.
Title: Approximation Algorithms for Matchings in Big Graphs
Speaker: | Alex Pothen |
Affiliation: | Purdue University |
Zoom: | Please email Emma Watson |
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.
Combinatorics & Optimization
University of Waterloo
Waterloo, Ontario
Canada N2L 3G1
Phone: 519-888-4567, ext 33038
PDF files require Adobe Acrobat Reader.
The University of Waterloo acknowledges that much of our work takes place on the traditional territory of the Neutral, Anishinaabeg and Haudenosaunee peoples. Our main campus is situated on the Haldimand Tract, the land granted to the Six Nations that includes six miles on each side of the Grand River. Our active work toward reconciliation takes place across our campuses through research, learning, teaching, and community building, and is centralized within our Office of Indigenous Relations.