.png){kind=icon}
.png){kind=icon}
Return
Lower Bounds for Weighted Matroid Problems
.png){kind=icon}
PRE
AI
DOI：10.1145/3774814.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We study a family of matroid optimization problems with a linear constraint (MOL). In these problems, we seek a subset of elements that optimizes (i.e., maximizes or minimizes) a linear objective function simultaneously subject to (i) a matroid independent set, or a matroid basis constraint and (ii) additional linear constraint. A notable member in this family is BUDGETED MATROmINDEPENDENT SET (BM), which can be viewed as classic 0/1-KNAPSACK with a matroid constraint. While special cases of BM, such as KNAPSACK WITH CARDINALITY CONSTRAINT and MULTIPLE-CHOICE KNAPSACK, admit a fully polynomial-time approximation scheme (Fully PTAS), the best-known result for BM on a general matroid is an Efficient PTAS. Prior to this work, the existence of a Fully PTAS for BM, and more generally, for any problem in the family of MOL problems, has been open. In this article, we answer this question negatively by showing that none of the (non-trivial) problems in this family admits a Fully PTAS. This resolves the complexity status of several well-studied problems. Our main result is obtained by showing first that EXACT WEIGHT MATROID BASIS (EMB) does not admit a pseudo-polynomial time algorithm. We then obtain unconditional hardness results for the family of MOL problems in the oracle model (even if randomization is allowed) and show that the same results hold when the matroids are encoded as part of the input, assuming P # NP.
Keywords:
Matroids
Knapsack
Linear Constraints
Lower Bounds
FPTAS
Budgeted Optimization
MOL Problems
Journal
A
IF:
1.4
Papers:
43
Citations:
1.1K