Title: Submodular function maximization via the multilinear relaxation and contention resolution schemes
|Affiliation:||University of Waterloo|
I will present a general framework for maximizing a nonnegative submodular set function $f$ subject to a variety of packing type constraints including multiple matroid constraints, knapsack constraints, and their intersections. Two takeaways from this talk will be: (i) a constant factor approximation algorithm to maximize the multilinear extension $F$ of $f$ over a solvable down-closed polytope; and (ii) an effective rounding strategy based on contention resolution schemes. In particular, we will see how contention resolution schemes for different polytopes can be combined to handle the intersection of different constraints.
Based on the work of Chekuri, Vondrak, and Zenklusen by the same title.
200 University Avenue West
Waterloo, ON N2L 3G1