Non-monotone Submodular Maximization over a Matroid in Offline and Streaming setting

In this talk, we present fixed-parameter tractable (FPT) algorithms for maximizing a non-monotone submodular function under a matroid constraint, where the matroid rank r is treated as a fixed parameter independent of the ground set size n. We develop two algorithms: one for the offline setting, achieving a near-optimal $1 - \frac{1}{e} - \epsilon$ approximation, and one for the random-order streaming setting, achieving a near-optimal $1/2 - \epsilon$ approximation with $\widetilde{O} (frac{r}{\mathrm{poly}(\epsilon)})$ memory. Notably, our offline result shows that---unlike in the polynomial-time regime---there is essentially no approximation gap between the monotone and non-monotone cases in the FPT setting. This talk is based on joint work with Adrian Vladu and Junyao Zhao (CNRS, IRIF, Université Paris Cité).