2025/09/01 by Nematollahi, Shamisa, Vladu, Adrian, Zhao, Junyao · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2509.01591
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 \widetildeO(\fracr\textrmpoly(ε)) memory, while our offline algorithm obtains a 1-(1)/(e)-ε approximation with n⋅ 2^\widetildeO(\fracr\textrmpoly(ε)) runtime and \widetildeO(\fracr\textrmpoly(ε)) 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.