Seminar: Separator-Based Algorithms for Graph Matching Problems

Nathaniel Lahn

PhD Candidate, Virginia Tech

Friday, November 22, 2019
11:15am - 12:15pm
2150 Torgersen Hall

nlahn

Abstract:

I consider the design of asymptotically faster algorithms for finding matchings on bipartite graphs, also commonly referred to as the assignment problem. Finding matchings is a fundamental optimization problem, where the goal is to create pairings of objects subject to given compatibility constraints. Specifically, I consider the special case where the graph has a small vertex separator. I will discuss my recent research, which focuses on how small separators can be used to speed up state-of-the-art matching algorithms. In addition, I will share some of my experiences as a graduate student working in theory of algorithms.

Biography:

Nathaniel is a third year Ph.D candidate in the computer science department at Virginia Tech, working under the advisement of Dr. Sharath Raghvendra. He primarily works on research in theory of algorithms, with a special focus towards problems in graph theory and computational geometry. His undergraduate degree in computer science is from Virginia Tech.