Matroid Optimization

Jon Lee

University of Michigan, Ann Arbor, USA.

University of Michigan, Ann Arbor, USA.

2014/12/04 *

Room 1409

**Thursday*** 4PM-5PMRoom 1409

Matroids can be seen an an abstraction for understanding the essence of algorithms for some classical graph problems: (i) optimum-weight spanning tree, and (ii) optimum-weight assignment. We will see some recent results showing how matroids have further natural roles in various combinatorial-optimization problems where some local-search and linear-programming-based algorithms find provably-good approximations. In particular, we will look at: (iii) constrained submodular-function maximization, (iv) the well-known matroid matching problem, and (v) various nonlinear-objective matroid-intersection problems.