Fixed-Parameter Tractable Submodular Maximization over a Matroid

In this paper, we design fixed-parameter tractable (FPT) algorithms for (non-monotone) submodular maximization subject to a matroid constraint, where the matroid rank $r$ is treated as a fixed parameter that is independent of the total number of elements $n$. We provide two FPT algorithms: one for the offline setting and another for the random-order streaming setting. Our streaming algorithm achieves a $\frac{1}{2}-\epsilon$ approximation using $\tilde{O}\left(\frac{r}{\text{poly}(\epsilon )}\right)$ memory, while our offline algorithm obtains a $1-\frac{1}{e}-\epsilon$ approximation with $n\cdot 2^{\tilde{O}\left(\frac{r}{\text{poly}(\epsilon )}\right)}$ runtime and $\tilde{O}\left(\frac{r}{\text{poly}(\epsilon )}\right)$ memory. Both approximation factors are near-optimal in their respective settings, given existing hardness results. In particular, our offline algorithm demonstrates that–unlike in the polynomial-time regime–there is essentially no separation between monotone and non-monotone submodular maximization under a matroid constraint in the FPT framework.