[Colloquium] Show and Tell Series at TTI-C (Raecle; TODAY,November 29th @ 12:15pm)

[Katherine Cumming]

TTI-C SHOW AND TELL SERIES
 
Presented by:  Toyota Technological Institute at Chicago
 
Speaker: Harald Raecke, TTI-C
Speaker's home page: http://www.tti-c.org/raecke.html
 
Time: Tuesday, November 29, 2005
Location: TTI-C Conference Room
Lunch Provided @ 12:00pm 
Seminar @ 12:15pm
 
Title: Oblivious Network Design
Abstract:
Consider the following network design problem: given a network $G = (V,E)$,
source-sink pairs $\{s_i, t_i\}$ arrive and desire to send a unit of flow
between themselves. The cost of the routing is this: ifedge $e$ carries a
total of $f_e$ flow (from all the terminal pairs), the cost is given by
$\sum_e \load(f_e)$, where $\load$ is some concave cost function; the goal
is to minimize the total cost incurred. However, we want the routing to be
oblivious: when terminal pair $(s_i, t_i)$ makes its routing decisions, it
does not know the current flow on the edges of the network, nor the identity
of the other pairs in the system. Moreover, it does not even know the
identity of the function $\load$, merely knowing that $\load$ is a concave
function of the total flow on the edge. How should it (obliviously) route
its one unit of flow? Can we get competitive algorithms for this problem?

We develop a framework to model oblivious network design problems (of which
the above problem is a special case), and give algorithms with
poly-logarithmic competitive ratio for problems in this framework (and hence
for this problem).

This is joint work with Anupam Gupta and MohammadTaghi Hajiaghayi. 
 
 
 
-----------------
If you have questions, or would like to meet the speaker, please contact
Katherine at 773-834-1994 or kcumming at tti-c.org.  For information on future
TTI-C talks or events, please go to the TTI-C Events page,
http://www.tti-c.org/events.html.  TTI-C (1427 East 60th Street, Chicago, IL
60637)
 
 
 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20051129/d92fc9c0/attachment.htm