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 |
Description
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.