2026-10-11T04:21:55Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25392 2026-03-19T12:04:26Z ddc:004 open_access

Fixed-Parameter Tractable Submodular Maximization over a Matroid Nematollahi, Shamisa Vladu, Adrian Zhao, Junyao Submodular maximization matroids parameterized complexity streaming algorithms 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 Õ(r/poly(ε)) memory, while our offline algorithm obtains a 1-(1)/(e)-ε approximation with n⋅ 2^{Õ(r/poly(ε))} runtime and Õ(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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shamisa Nematollahi and Adrian Vladu and Junyao Zhao 2026 Is Part Of LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2026.105 urn:nbn:de:0030-drops-253924 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.105 eng https://creativecommons.org/licenses/by/4.0/legalcode