Lower Bounds for Matroid Optimization Problems with a Linear Constraint
arxiv(2023)
摘要
We study a family of matroid optimization problems with a linear constraint
(MOL). In these problems, we seek a subset of elements which optimizes (i.e.,
maximizes or minimizes) a linear objective function subject to (i) a matroid
independent set, or a matroid basis constraint, (ii) additional linear
constraint. A notable member in this family is budgeted matroid independent 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 paper, 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. This distinguishes EMB from the special cases
of k-subset sum and EMB on a linear matroid, which are solvable in
pseudo-polynomial time. 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. For the hardness proof of EMB, we introduce
the Π-matroid family. This intricate subclass of matroids, which exploits
the interaction between a weight function and the matroid constraint, may find
use in tackling other matroid optimization problems.
更多查看译文
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要