Return to Colloquia & Seminar listing

### Recent progress in matroid optimization

**Algebra & Discrete Mathematics**

Speaker: | Jon Lee, IBM Research |

Location: | 2112 MSB |

Start time: | Thu, Apr 23 2009, 2:10PM |

Matroids were explicitly introduced by Whitney (1935) as a unified abstraction of a combinatorial aspect of linear dependence and of the incidence relations of acyclic edge subsets of a finite graph. Even before that, matroid properties were implicitly used in graph algorithmics (1926). As matroids have been developed as a mathematical subject, there has been a parallel development on the algorithmic side. I will survey what is known, and I will give details of recent developments for optimizing nonlinear functions over the independent sets or bases of one or two matroids.