Matroid Optimization
Jon Lee
University of Michigan, Ann Arbor, USA.
University of Michigan, Ann Arbor, USA.
2014/12/04 *Thursday* 4PM-5PM
Room 1409
Room 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.