Submodular Optimization with Contention Resolution Extensions

This paper considers optimizing a submodular function subject to a set of downward closed constraints. Previous literature on this problem has often constructed solutions by (1) discovering a fractionalsolution to the multi-linear extension and (2) rounding this solution to an integral solution via acontention resolution scheme. This line of research has improved results by either optimizing (1) or (2).Diverging from previous work, this paper introduces a principled method called contentionresolution extensions of submodular functions. A contention resolution extension combines thecontention resolution scheme into a continuous extension of a discrete submodular function. Thecontention resolution extension can be defined from effectively any contention resolution scheme. Inthe case where there is a loss in both (1) and (2), by optimizing them together, the losses can becombined resulting in an overall improvement. This paper showcases the concept by demonstratingthat for the problem of optimizing a non-monotone submodular subject to the elements forming anindependent set in an interval graph, the algorithm gives a .188-approximation. This improves uponthe best known approximation.