Metraipolis › archive › dc_87644aed36f8

Tight Approximation Results for Matroid Optimization with a Linear Constraint — arXiv:2609.28708

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.28708
License (as archived)
CC0-1.0
Archived
2026-10-08T07:26:36.692Z
SHA-256 of the archived text
951e45187945c53fd1c2111c96bd43720371b1ca5d2429d2ce712885aac7d0b4
Stable URL of this page
https://metraipolis.com/documento/dc_87644aed36f8

How to cite

Tight Approximation Results for Matroid Optimization with a Linear Constraint — arXiv:2609.28708 — arXiv (en), https://arxiv.org/abs/2609.28708 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_87644aed36f8 (Metraipolis archive dc_87644aed36f8, sha256 951e45187945c53fd1c2111c96bd43720371b1ca5d2429d2ce712885aac7d0b4)
BibTeX
@misc{dc87644aed36f8,
  title = {Tight Approximation Results for Matroid Optimization with a Linear Constraint — arXiv:2609.28708},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.28708},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_87644aed36f8; sha256 951e45187945c53fd1c2111c96bd43720371b1ca5d2429d2ce712885aac7d0b4},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.28708. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 $\epsilon>0$, we present an algorithm running in time $|E|^{O(1)} (1/{\epsilon^2})^{O(1/{\epsilon})}$ that outputs a feasible solution S whose value is at most $(1+\epsilon)OPT$ for minimization variants and at least $(1-\epsilon)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.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-25 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2609.28708 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-08T06:44:29.080Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-25?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).