Maximizing Non-Monotone Submodular Functions over Small Subsets: Beyond $1\mathrm{/}2$-Approximation

In this work we give two new algorithms that use similar techniques for (non-monotone) submodular function maximization subject to a cardinality constraint. The first is an offline fixed parameter tractable algorithm that guarantees a $0.539$-approximation for all non-negative submodular functions. The second algorithm works in the random-order streaming model. It guarantees a $(1\mathrm{/}2+c)$-approximation for symmetric functions, and we complement it by showing that no space-efficient algorithm can beat $1\mathrm{/}2$ for asymmetric functions. To the best of our knowledge this is the first provable separation between symmetric and asymmetric submodular function maximization.