Chandra Chekuri

Submodular Maximization over Bipartite Perfect Matchings and Matroid Intersection Bases

Motivated by applications in fairness and foundational questions, we consider the problem of maximizing a monotone submodular function $f\colon 2^E \rightarrow \mathbb{R}_+$ over maximum cardinality sets in the intersection of two matroids on a common ground set $E$. An important special case is submodular perfect matc...