Tight Approximation Results for Matroid Optimization with a Linear Constraint

Abstract

We study the following class of matroid optimization problems with a linear constraint (P-MOL). Given a matroid M=(E,I), two weight functions $v,w:E\to R_{\ge 0}$, and a threshold $L\in R_{\ge 0}$, find $opt v(S)$ where S is either an independent set or a base of M satisfying a budget-type constraint: $w(S)\le L$ or $w(S)\ge L$, and $opt\in\{min,max\}$. P-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)\ge L$. Our main result is a unified EPTAS for all nontrivial P-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/{ε^2})^{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 P-MOL, as none of these problems admits an FPTAS (Doron-Arad, Kulik and Shachnai, ICALP'24). Finally, we separate the P-MOL family from its extension to matroid intersection. We show that an EPTAS is unlikely to exist for the matroid intersection variant of P-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.

The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.

More in Data Structures & Algorithms

• arXiv preprint · 23 September 2026

  Boyer-Moore Variants for Indeterminate String Matching and Experimental Evaluation

  Neerja Mhaskar and Nivetha Raj Pappuraj
• arXiv preprint · 24 September 2026

  A Deterministic Polynomial Kernel for Odd Cycle Transversal

  Tomohiro Koana and Soh Kumabe
• arXiv preprint · 23 September 2026

  $c$-Packedness versus $λ$-Low-Density in Geometric Graphs: Theory and Practice

  Gregor Diatzko, Félix Lasseux and Sabine Storandt
• arXiv preprint · 24 September 2026

  Parameterized Complexity of Spanner Problems with Independent Weights and Lengths

  Marius Bächler, Markus Chimani and Henning Jasper
• arXiv preprint · 23 September 2026

  Sampling Line-Graph Colorings with Constant Extra Colors

  Alireza Haqi

All new papers in Data Structures & Algorithms