Yuval Filmus: Monotone submodular maximization over a matroid using local search

Lunch is served at 12:00 noon (register at doodle.com/v5wyzey6usa78yu4 ). The presentation starts at 12:10 pm (note the time) and ends at 1 pm. Those who wish reconvene after a break for roughly two more hours of more technical discussions (ending at the latest 3 pm).

Abstract

Maximum coverage is the relative of set cover in which instead of trying to cover the entire universe with as few sets as possible, we are trying to cover as many elements as possible using a fixed number of sets. The greedy algorithm gives a 1-1/e approximation. Surprisingly, Feige proved that this ratio is optimal unless P=NP.

Things get more complicated when we replace the cardinality constraint on the sets with a matroid constraint (say, there are K types of sets, and we should choose at most one of each type). The greedy algorithm now gives only a 1/2 approximation. Calinescu et al. developed a sophisticated algorithm that gives a 1-1/e approximation. Their algorithm combines gradient ascent on a continuous relaxation with optimal rounding, and also works in the more general setting of monotone submodular maximization.

We show that non-oblivious local search also gives the optimal approximation ratio. The auxiliary objective function, with respect to which the local search proceeds, gives more weight to elements covered multiple times in the current solution. We also extend our algorithm to the setting of monotone submodular maximization.  

Joint work with Justin Ward.