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.