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