Randomized Algebraic Algorithms for Matroid and Matching Problems
Speaker: Nick Harvey , MIT CSAIL
Date: February 23 2006
Time: 4:00PM to 5:15PM
Location: 32-G575
Host: Madhu Sudan, MIT CSAIL
Contact: Joanne Hanley, 617.253.6054, joanne@csail.mit.edu
Relevant URL: http://theory.csail.mit.edu/~madhu/algcomp/nick-abs.htmlAbstract:
The task of finding a maximum matching in a graph is one of the classical problems in the theory of algorithms, inspiring the definition of the class P. Till recently, the fastest algorithm for this task took O(n^2.5) steps in an n vertex (dense) graph. But an exciting development due to Mucha and Sankoswki (FOCS '04) dropped the running time to O(n^w) where w < 2.38 is the exponent of matrix multiplication, with a randomized algorithm. However, their result was quite complicated, relying on certain structural decompositions of graphs and complicated data structures to maintain certain properties dynamically.
In this talk, I will present two new results: The first is a simple randomized algorithm achieving the same result, allowing for a self-contained presentation of this result. The second is an extension of this algorithm to the task of matroid intersection (for linear matroids over any field).
See other events that are part of Algorithms and Complexity Spring 2006
See other events happening in February 2006
