Mathematics Colloquia and Seminars

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.