Approximation Algorithms for Graph Routing Problems
Julia Chuzhoy
Chicago University
MPI Colloquium Series Distinguished Speaker
Julia Chuzhoy is an Associate Professor at the Toyota Technological Institute at Chicago (TTIC). She received her Ph.D. in Computer Science from Technion, Israel in 2004, and has spent several years as a postdoc at MIT, University of Pennsylvania and Institute for Advanced Study, before joining TTIC in 2007. Her research area is theoretical computer science, with the main emphasis on the design and the analysis of approximation algorithms for NP-hard problems. She is a receipient of the NSF Career award, Sloan Research Fellowship, and she was an invited speaker at the 2014 International Congress of Mathematicians. http://ttic.uchicago.edu/~cjulia/
In a typical routing problem, we are given a graph G, and a collection (s_1,t_1),…,(s_k,t_k) of pairs of vertices, called demand pairs, that we are interested to route. In order to route a demand pair (s_i,t_i), we need to choose a path in G, connecting s_i to t_i. Our goal is usually to route as many of the demand pairs as possible, while keeping the congestion of the routing - the maximum load on any vertex or an edge of G - as small as possible. This general framework gives rise to a number of basic and widely studied graph routing problems, that have lead to the development of a rich toolkit of algorithmic techniques, as well as structural graph theoretic results. In this talk we will survey some of the central routing problems, the new and the old techniques used for approximating them, and some connections between approximation algorithms and graph theory arising in the context of graph routing.