If it is Good Then Drop it -- a Spiteful Poisson Process for Submodular Maximization

Abstract

We study the problem of maximizing a general and not necessarily monotone submodular function subject to a matroid independence constraint. This problem has a rich history, with multiple algorithms using both discrete and continuous methods. Recently, [Ganz-Rozenman, Kulik, Schwartz and Singh STOC `26] presented a novel hybrid approach based on a Poisson process that aims to combine the strengths of both discrete and continuous methods for the special case of the problem where the submodular function is monotone. Our main result is a new Poisson process based hybrid algorithm that works for both non-monotone and monotone submodular functions, achieving an approximation of $ \frac{1}{e}$ for the former and $1-\frac{1}{e}$ for the latter. The algorithm always maintains a feasible set and at random times governed by the Poisson process it performs a single element swap based on a best response set. The new idea is that our algorithm is spiteful as it can purposefully discard an element that is in both the current set and the best response set. Surprisingly, this spiteful step does not harm the approximation our algorithm achieves for monotone submodular functions but is necessary for the non-monotone case. As applications, we obtain fast approximation algorithms for maximizing non-monotone submodular function subject to a general matroid independence constraint as well as faster algorithms for a partition matroid.