Recent progress in matroid optimizationAlgebra & Discrete Mathematics
|Speaker:||Jon Lee, IBM Research|
|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.