Submodular Maximization under Matroid Constraints in Combinatorial Optimization
Submodular set functions capture diminishing returns: adding an element to a smaller set yields at least as much marginal gain as adding it to a larger set. Maximizing a monotone submodular utility over a discrete ground set subject to matroid constraints (a cardinality bound, or a partition constraint) is NP-hard, but the sequential greedy algorithm achieves a guaranteed constant-factor optimality bound, and the continuous greedy algorithm improves it via a multilinear relaxation. Students learn the definitions, the greedy algorithms and their approximation guarantees, and how the same framework extends to distributed, multi-agent settings.
Submodular Maximization Subject to Uniform and Par- tition Matroids: From Theory to Practical
A tutorial exposition of submodular maximization: choosing a subset S of a finite ground set to maximize a set function f(S) that exhibits diminishing returns (submodularity), subject to matroid cons…