Monday, March 03, 2008
11:00 AM
CSB 209
Virginia Vassilevska
Carnegie Mellon University
Algorithms for Path Problems
My talk will discuss two variants of the shortest paths problem, which optimize different measures. One variant maximizes the minimum edge on the path (instead of minimizing the sum of edge weights), and the other minimizes the last edge on a path with the additional condition that the consecutive edge weights on the path form a nondecreasing sequence. Finding best paths with respect to these measures has many applications, e.g., creating good flight itineraries and maximizing bandwidth in packet routes, even has applications in fuzzy logic. Furthermore, my work has shown that one can obtain really efficient algorithms for these problems. The goal of the talk is to show some of my techniques on attacking path problems. As an example for a single source path problem, I will concentrate on minimum nondecreasing paths. This is based on my recent sole-authored paper that appeared in SODA08. As an example for an all-pairs path problem, I will outline the first subcubic algorithm for all-pairs maximum bottleneck paths. This work is joint with Ryan Williams and Raphael Yuster and appeared in STOC07.

Bio: Virginia Vassilevska is currently a computer science graduate student at Carnegie Mellon University, from which she also received her M.S. Her thesis will be on ``Efficient Algorithms for Path Problems in Weighted Graphs,'' and her advisor is Prof. Guy Blelloch. Her undergraduate work was done at the California Institute of Technology, where she graduated with honors in 2003 with a double major in mathematics and engineering and applied science (CS). She is broadly interested in algorithms, data structures, and approximability, with a particular focus on graph algorithms.

Refreshments will be provided at 10:45