The Birkhoff--von Neumann decomposition expresses a doubly stochastic
matrix as a convex combination of permutation matrices. This talk
will be an introduction to this decomposition. We are going to see
its use in solving sparse linear systems, and investigate some
algorithmic and combinatorial problems associated with it.
This talk contains results from joint work with Michele Benzi (Emory Univ.,
Atlanta), Fanny Dufosse (Inria, France), Kamer Kaya (Sabanci Univ, Turkey),
and Ioannis Panagiotas (ENS Lyon, France).