[Colloq] Reminder: 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)



_______________________________________________
Colloq mailing list
Colloq at lists.ccs.neu.edu
https://lists.ccs.neu.edu/bin/listinfo/colloq