2026-07-24T05:02:11Z https://drops.dagstuhl.de/oai
oai:drops-oai.dagstuhl.de:19432 2024-03-06T11:04:02Z ddc:004 open_access
Budgeted Matroid Maximization: a Parameterized Viewpoint Doron-Arad, Ilan Kulik, Ariel Shachnai, Hadas budgeted matching budgeted matroid intersection knapsack problems FPT-approximation scheme We study budgeted variants of well known maximization problems with multiple matroid constraints. Given an 𝓁-matchoid β„³ on a ground set E, a profit function p:E β†’ ℝ_{β‰₯ 0}, a cost function c:E β†’ ℝ_{β‰₯ 0}, and a budget B ∈ ℝ_{β‰₯ 0}, the goal is to find in the 𝓁-matchoid a feasible set S of maximum profit p(S) subject to the budget constraint, i.e., c(S) ≀ B. The budgeted 𝓁-matchoid (BM) problem includes as special cases budgeted 𝓁-dimensional matching and budgeted 𝓁-matroid intersection. A strong motivation for studying BM from parameterized viewpoint comes from the APX-hardness of unbudgeted 𝓁-dimensional matching (i.e., B = ∞) already for 𝓁 = 3. Nevertheless, while there are known FPT algorithms for the unbudgeted variants of the above problems, the budgeted variants are studied here for the first time through the lens of parameterized complexity. We show that BM parametrized by solution size is W[1]-hard, already with a degenerate single matroid constraint. Thus, an exact parameterized algorithm is unlikely to exist, motivating the study of FPT-approximation schemes (FPAS). Our main result is an FPAS for BM (implying an FPAS for 𝓁-dimensional matching and budgeted 𝓁-matroid intersection), relying on the notion of representative set - a small cardinality subset of elements which preserves the optimum up to a small factor. We also give a lower bound on the minimum possible size of a representative set which can be computed in polynomial time. Schloss Dagstuhl – Leibniz-Zentrum fΓΌr Informatik Ilan Doron-Arad and Ariel Kulik and Hadas Shachnai 2023 Is Part Of LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2023.13 urn:nbn:de:0030-drops-194329 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.13 eng https://creativecommons.org/licenses/by/4.0/legalcode