2026-09-10T09:44:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27735 2026-09-09T12:19:35Z ddc:004 open_access

Tight Approximation Results for Matroid Optimization with a Linear Constraint Doron-Arad, Ilan Shachnai, Hadas Shmerler, Gilad Matroids Knapsack Linear Constraints EPTAS Budgeted Optimization MOL Problems We study the following class of matroid optimization problems with a linear constraint (𝒫-MOL). Given a matroid ℳ = (E,ℐ), two nonnegative weight functions v,w:E → ℝ_{≥ 0}, and a threshold L ∈ ℝ_{≥ 0}, find opt v(S) where S is either an independent set or a base of ℳ satisfying a budget-type constraint: w(S) ≤ L or w(S) ≥ L, and opt ∈ {min,max}. 𝒫-MOL provides a unified representation for a broad family of NP-hard optimization problems, including budgeted matroid independent set, constrained minimum-basis, and knapsack-cover variants with a matroid constraint. Also, it naturally extends to multiple matroid constraints. In particular, we consider the matroid intersection cover (MIC) problem, where feasibility is defined by the common independent sets of two matroids and one seeks minimum v(S) subject to w(S) ≥ L. Our main result is a unified efficient polynomial-time approximation scheme (EPTAS) for all nontrivial 𝒫-MOL variants, obtained by generalizing a technique of Hassin and Levin (SIAM J. Comput., 2004) for solving the constrained minimum spanning tree problem. Specifically, for any fixed ε > 0, we present an algorithm running in time |E|^O(1) ⋅ (1/ε²)^O(1/ε) that outputs a feasible solution S whose value is at most (1+ε)OPT for minimization variants and at least (1-ε)OPT for maximization variants. This resolves the complexity status of all members of 𝒫-MOL, as none of these problems admits a fully polynomial-time approximation scheme (Doron-Arad, Kulik and Shachnai, ICALP'24). Finally, we separate the 𝒫-MOL family from its extension to matroid intersection. We show that an EPTAS is unlikely to exist for the matroid intersection variant of 𝒫-MOL under a covering constraint, whereas an EPTAS is known to exist under a budget constraint. This highlights a qualitative difference between these two types of linear constraints that does not arise in the single-matroid setting. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ilan Doron-Arad and Hadas Shachnai and Gilad Shmerler 2026 Is Part Of LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2026.18 urn:nbn:de:0030-drops-277354 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.18 eng https://creativecommons.org/licenses/by/4.0/legalcode