Lower Bounds for Matroid Optimization Problems with a Linear Constraint
Preprint
Abstract
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 \neq 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.
Keywords
All Related Versions
This publication has 20 references indexed in Scilit:
- An FPTAS for budgeted laminar matroid independent setOperations Research Letters, 2023
- A simple PTAS for weighted matroid matching on strongly base orderable matroidsDiscrete Applied Mathematics, 2014
- There is no EPTAS for two-dimensional knapsackInformation Processing Letters, 2010
- Budgeted Matching and Budgeted Matroid Intersection Via the Gasoline Puzzle2008
- A fully polynomial bicriteria approximation scheme for the constrained spanning tree problemOperations Research Letters, 2004
- A note on maximizing a submodular set function subject to a knapsack constraintOperations Research Letters, 2004
- On bicriterion minimal spanning trees: An approximationComputers & Operations Research, 1996
- The random oracle hypothesis is falseJournal of Computer and System Sciences, 1994
- Random pseudo-polynomial algorithms for exact matroid problemsJournal of Algorithms, 1992
- Matroid intersection algorithmsMathematical Programming, 1975