Speaker
Description
Matching is one of the most fundamental combinatorial objects in both graph theory and combinatorial optimization. Moreover, a lot of variants of have been studied in both exact and approximation settings. In the first part of my talk, I will present several classical graph matching algorithms and illustrate some intuitions and techniques behind them.
Then I will focus on the geometric setting. Suppose we are given a set of points in a metric space, and we are asked to find a matching between them. Here, our underlying graph can be defined as a complete graph. This geometric matching problem provides both theoretical insights and real-world applications. In the second part of my talk, I will cover geometric variants of the aforementioned matching-like problems. This part shows that geometric tools can significantly improve the running time of the classical graph matching algorithms.
