{"ID":2875997,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.01591","arxiv_id":"2509.01591","title":"Fixed-Parameter Tractable Submodular Maximization over a Matroid","abstract":"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}-\\varepsilon$ approximation using $\\widetilde{O}\\left(\\frac{r}{\\textrm{poly}(\\varepsilon)}\\right)$ memory, while our offline algorithm obtains a $1-\\frac{1}{e}-\\varepsilon$ approximation with $n\\cdot 2^{\\widetilde{O}\\left(\\frac{r}{\\textrm{poly}(\\varepsilon)}\\right)}$ runtime and $\\widetilde{O}\\left(\\frac{r}{\\textrm{poly}(\\varepsilon)}\\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.","short_abstract":"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 a...","url_abs":"https://arxiv.org/abs/2509.01591","url_pdf":"https://arxiv.org/pdf/2509.01591v1","authors":"[\"Shamisa Nematollahi\",\"Adrian Vladu\",\"Junyao Zhao\"]","published":"2025-09-01T16:25:19Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}