[Colloq] PhD Dissertaion Defense by Jiangzhuo Chen, Monday Aug. 8, 2pm

[Rachel Kalweit]

College of Computer and Information Science

PhD Dissertation Defense:
Jiangzhuo Chen

Title:
Confluent Flows


Monday, August 8, 2005
2:00pm
366 West Village H

Abstract:
This dissertation concerns the design of algorithms for finding 
confluent flows in networks. A flow of a given commodity in a network is 
confluent if at any node all the outgoing flows leave along a single 
edge. The notion of confluence is motivated by various network 
applications including Internet routing and content delivery networks, 
roadway routing, and evacuation.  We establish a model for confluent 
flows and develop approximation algorithms and hardness results for 
several optimization problems in this model.

For single commodity confluent flows, we have identified nearly tight 
bounds on minimum-congestion and maximum-demand confluent flows when all 
edges or nodes have uniform capacities. We further extend the model to 
the multicommodity setting and study the minimum-congestion problem, 
which is mainly motivated by Internet routing. For this problem, we have 
designed a simple approximation algorithm that is amenable to a 
distributed implementation. Our algorithm provides analytically better 
capacity in Internet-like networks, compared with shortest path routing 
algorithms.
Our simulations strongly support our analytical results and motivate 
implementations of our multicommodity confluent flow algorithms in 
network routing applications.

DISSERTATION COMMITTEE:
Agnes Chan (NU)
Sanjeev Khanna (U. Penn)
Rajmohan Rajaraman (NU, advisor)
Ravi Sundaram (NU, co-advisor)
Anil Vullikanti (Virginia Tech)