Sunday, March 26, 14:15-15:15
at 14:00
Schreiber Building, Room 309
The application of MST for maximal tree packing is new (joint work
with David Karger) and when boot-strapped, it yields a fully-dynamic
polylogarithmic 2-approximation algorithms for min-cut.
Finally, on the more practical side, we will discuss how output
senstive algorithms for dynamic shortest paths have been applied
successfully in local search algorithms for improving routing on
the internet, roughly doubling the capacity.
For colloquium schedule, see http://www.math.tau.ac.il/~zwick/colloq.html