Department of Mathematics FAS Harvard University One Oxford Street Cambridge MA 02138 USA Tel: (617) 495-2171 Fax: (617) 495-5132

Math table October 2, 2019

Speaker: Michael Kielstra
Title: The Fisherman, the Graduate, and the Robot: Linear Programming for Applied Graph Theory
Abstract: Graphs, which are collections of vertices and edges joining them, give us visual representations of networks. A perfect matching is a set of edges of a graph such that every vertex is covered by exactly one edge in the matching. These types of matchings can be used to find ways to allocate resources or assign tasks to large networks of people or organizations. Methods of finding perfect matchings have been put forward and refined since Jack Edmonds found the first one in 1958. In this talk we will discuss Edmond's algorithm for finding perfect matchings as well as recent improvements on it.

Privacy Digital Accessibility