Technion, IEM faculty - Operations Research seminar
 
Speaker: Oren Weimann
 
Title: Fault-tolerant shortest paths
 
Date: 21/03/2011
 
Time: 12:30
 
Place: Bloomfield-527
 
Abstract:  <http://ie.technion.ac.il/seminar_files/1299578276_Oren_Weimann_seminar.doc>
 
Or see below:
 
Abstract: In a network G whose edges occasionally fail, a shortest path P between two nodes s and t may have to
change accordingly. The "replacement paths" problem asks to compute, for every edge e in P, the shortest s-to-t path
that avoids e. This is a generalization of the fundamental shortest paths problem that is better suited for
real-world dynamic networks. In auction theory, the replacement paths problem is used to compute the Vickrey pricing
of edges owned by selfish agents. In my talk, I will present an O(Mn^{2.584}) time algorithm for the replacement
paths problem on general networks with edge-lengths in {-M,...,M}, and an O(n log^2n) time algorithm that works for
arbitrary edge-lengths provided that the underlying network is planar.
 
---------------------------------------------------------
Technion Math. Net (TECHMATH)
Editor: Michael Cwikel   <techm@math.technion.ac.il> 
Announcement from:  <levinas@techunix.technion.ac.il>