MPI-INF Logo
Campus Event Calendar

Event Entry

What and Who

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/
AG 1, AG 2, AG 3, AG 4, AG 5, SWS, RG1, MMCI  
Public Audience
English

Date, Time and Location

Tuesday, 7 June 2016
11:00
60 Minutes
E1 4
024
Saarbrücken

Abstract

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.

Contact

Petra Schaaf
5000
--email hidden
passcode not visible
logged in users only

Petra Schaaf, 06/01/2016 11:16 -- Created document.