Matrix Rank and Combinatorial Optimization
Lap Chi Lau
Recorded 14 June 2012 in Lausanne, Vaud, Switzerland
Event: SuRI - I&C - Summer Research Institute
First we survey some previous work on designing fast linear algebraic algorithms for combinatorial optimization problems. Then we present a new algebraic formulation for computing edge connectivities, using the ideas developed in network coding. Then we present a fast "combinatorial" algorithm for computing matrix rank using expander graphs, and discuss its applications. Finally we conclude with some open problems in this area.
Watched 7636 times.Watch