Matroid optimization problems solved efficiently with new approximation method
Tight Approximation Results for Matroid Optimization with a Linear Constraint
Data Structures and Algorithms
Summary
Optimization problems that involve choosing elements under certain rules are often very hard to solve exactly. The authors studied a broad family of such problems involving matroids and additional linear constraints, like budget limits or minimum requirements. They designed an efficient approximation method that, for any desired accuracy, finds solutions very close to the best possible and runs in reasonable time. Their results settle the difficulty of these problems and show important differences depending on the types of constraints used.
What this means in practice
- •For operations research teams: Efficiently approximate solutions to matroid optimization problems constrained by linear budgets or requirements in logistics and resource allocation.
- •For network infrastructure planners: Plan network designs under combined independence and resource constraints using approximation schemes that guarantee near-optimal costs or capacities.
A theory result. No direct application yet.
Authors
Ilan Doron-Arad, Hadas Shachnai, Gilad Shmerler
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.