Budgeted Matroid Maximization: a Parameterized Viewpoint
share
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.
READ FULL TEXT