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 1/2 − ε approximation using O~(r / poly(ε)) memory, while our offline algorithm obtains a 1 − 1/e − ε approximation with n · 2^{O~(r / poly(ε))} runtime and O~(r / poly(ε)) 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. This is joint work with Shamisa Nematollahi and Adrian Vladu.

Junyao Zhao is an FSMP postdoctoral fellow at IRIF (CNRS & Université Paris Cité). He did his Ph.D. in computer science at Stanford University, advised by Aviad Rubinstein. Before that, he obtained an M.Sc. with distinction in computer science from ETH Zürich and a B.Eng. in software engineering from Tongji University. His current research focuses on algorithmic game theory, submodular optimization, and online learning. Specific topics include: beyond-worst-case analysis, communication complexity, simplicity vs. efficiency in algorithmic mechanism design, and strategic robustness in online learning.