Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Approximation Algorithms for Graph Routing Problems
Speaker:Julia Chuzhoy
coming from:Chicago University
Speakers Bio: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.

Event Type:MPI Colloquium Series Distinguished Speaker
Visibility:D1, D2, D3, D4, D5, SWS, RG1, MMCI
We use this to send out email in the morning.
Level:Public Audience
Date, Time and Location
Date:Tuesday, 7 June 2016
Duration:60 Minutes
Building:E1 4
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.
Name(s):Petra Schaaf
EMail:--email address not disclosed on the web
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):

Petra Schaaf/AG5/MPII/DE, 06/01/2016 11:11 AM
Last modified:
halma/MPII/DE, 11/07/2018 04:52 PM
  • Petra Schaaf, 06/01/2016 11:16 AM -- Created document.