#  Lower Bounds for Matroid Optimization Problems with
a Linear Constraint

Ilan Doron-Arad Computer Science Department, Technion, Haifa, Israel. idoron-
<EMAIL_ADDRESS>Ariel Kulik CISPA Helmholtz Center for Information
Security, Saarland Informatics Campus, Germany<EMAIL_ADDRESS>Hadas
Shachnai Computer Science Department, Technion, Haifa, Israel.
<EMAIL_ADDRESS>
###### 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 $\textnormal{P}\neq\textnormal{NP}$. For the hardness
proof of EMB, we introduce the $\Pi$-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.

##  1 Introduction

Matroids are simple combinatorial structures, providing a unified abstraction
for independence systems such as linear independence in a vector space, or
cycle-free subsets of edges in a given graph. A matroid is a set system
$(E,{\mathcal{I}})$, where $E$ is a finite set and ${\mathcal{I}}\subseteq
2^{E}$ are the independent sets (IS) such that $(i)$
$\emptyset\in{\mathcal{I}}$, $(ii)$ for all $A\in{\mathcal{I}}$ and
$B\subseteq A$ it holds that $B\in{\mathcal{I}}$, and $(iii)$ for all
$A,B\in{\mathcal{I}}$ where $|A|>|B|$, there is $e\in A\setminus B$ such that
$B\cup\\{e\\}\in{\mathcal{I}}$.111Properties $(ii)$ and $(iii)$ are known as
hereditary property, and exchange property.

While serving as a generic abstraction for numerous applications, matroids
possess useful combinatorial properties that allow the development of
efficient algorithms. These algorithms include such canonical results as the
classic greedy approach for finding a maximum weight independent set of a
matroid (see, e.g., [13]), Edmond’s algorithm for matroid partitioning [20],
and Lawler’s algorithm for matroid intersection [30]. In all of the above,
polynomial running time is enabled due to the structure of the problem $-$ a
single objective function with a matroid constraint. However, in many natural
applications, there is an added linear constraint.

Consider, for example, the problem of finding a maximum independent set in a
matroid subject to a budget constraint. Formally, we are given a set of
elements $E$, a membership oracle for a collection of independent sets
${\mathcal{I}}\subseteq 2^{E}$ of a matroid $(E,{\mathcal{I}})$, a budget
$L>0$, a weight function $w:E\to\mathbb{R}_{\geq 0}$, and a value function
$v:E\rightarrow\mathbb{R}_{\geq 0}$. A solution for the problem is an
independent set $S\in{\mathcal{I}}$ of total weight at most $L$, i.e.,
$w(S)\leq L$.222For every set $X$, a function $f:X\rightarrow\mathbb{R}_{\geq
0}$ and $Y\subseteq X$ we define $f(Y)=\sum_{e\in Y}f(e)$. The value of a
solution $S$ is given by $v(S)$, and the objective is to find a solution of
maximum value. This problem, known as budgeted matroid independent set (BM),
is a generalization of the classic $0/1$-knapsack, which is NP-hard and
therefore unlikely to admit an exact polynomial-time algorithm. Thus,
obtaining efficient approximations has been a main focus in the study of BM.

For an instance $I$ of an optimization problem ${\mathcal{G}}$, let
$\textnormal{OPT}_{{\mathcal{G}}}(I)$ be the value of an optimal solution for
$I$. For some $\rho\geq 1$, a $\rho$-approximate solution $S$ for $I$ is a
solution of value $v\geq\frac{\textnormal{OPT}_{{\mathcal{G}}}(I)}{\rho}$
($v\leq\rho\cdot\textnormal{OPT}_{{\mathcal{G}}}(I)$) if ${\mathcal{G}}$ is a
maximization (minimization) problem. We say that ${\mathcal{A}}$ is a
randomized $\rho$-approximation algorithm for ${\mathcal{G}}$ if, given an
instance $I$ of ${\mathcal{G}}$, ${\mathcal{A}}$ returns with probability at
least $\frac{1}{2}$ a $\rho$-approximate solution for $I$ $-$ if a solution
exists. If no solution exists $-$ ${\mathcal{A}}$ returns that $I$ does not
have a solution.

Let $|I|$ be the encoding size of an instance $I$ of a problem
${\mathcal{G}}$. A (randomized) polynomial-time approximation scheme (PTAS)
for ${\mathcal{G}}$ is a family of algorithms
$(A_{{\varepsilon}})_{{\varepsilon}>0}$ such that, for any ${\varepsilon}>0$,
$A_{{\varepsilon}}$ is a (randomized) polynomial-time
$(1+{\varepsilon})$-approximation algorithm for ${\mathcal{G}}$. A
(randomized) Efficient PTAS (EPTAS) is a (randomized) PTAS
$(A_{{\varepsilon}})_{{\varepsilon}>0}$ with running time of the form
$f\left(\frac{1}{{\varepsilon}}\right)\cdot|I|^{O(1)}$, where $f$ is an
arbitrary computable function. The strong dependence of run-times on the error
parameter, ${\varepsilon}>0$, often renders the above schemes highly
impractical. This led to the study of the following more desirable class of
schemes. A (randomized) approximation scheme
$(A_{{\varepsilon}})_{{\varepsilon}>0}$ is a (randomized) Fully PTAS (FPTAS)
if the running time of $A_{{\varepsilon}}$ is of the form
${\left(\frac{|I|}{{\varepsilon}}\right)}^{O(1)}$.333To better distinguish
between EPTAS and FPTAS, we use throughout the paper Efficient PTAS and Fully
PTAS.

In the past decades, BM was shown to admit a PTAS [2, 12, 24], and more
recently an Efficient PTAS [19, 18]. As the special case of $0/1$-knapsack
admits a Fully PTAS, it is natural to explore the existence of a Fully PTAS
for BM. There are known Fully PTASs for BM on restricted families of matroids.
This includes knapsack with a cardinality constraint [7], multiple-choice
knapsack [31], and BM with laminar matroid constraint [15]. However, the
question of whether BM admits a Fully PTAS on general matroids remained open.

In this paper, we resolve this question negatively for BM and other
fundamental matroid optimization problems with a linear constraint.

###  1.1 Our Results

For a matroid ${\mathcal{M}}=(E,{\mathcal{I}})$ we define
$\textnormal{IS}({\mathcal{M}})={\mathcal{I}}$ and
$\textnormal{bases}({\mathcal{M}})=\\{S\in{\mathcal{I}}~{}|~{}|S|=\textsf{rank}({\mathcal{M}})\\}$,
where $\textsf{rank}({\mathcal{M}})=\max_{T\in{\mathcal{I}}}|T|$ is the rank
of ${\mathcal{M}}$, i.e., the maximum cardinality of an independent set. We
study a family of matroid optimization problems with a linear constraint
(MOL). Problems in this family are characterized by three parameters:

  1. (i)

The optimization objective opt $-$ either the operator $``\max"$ or $``\min"$.

  2. (ii)

A matroid feasibility constraint ${\mathcal{F}}$ $-$ either the independent
sets of a matroid, or the set of bases of a matroid. The feasibility
constraint is ${\mathcal{F}}\in\\{\textnormal{IS},\textnormal{bases}\\}$.

  3. (iii)

A relation $\triangleleft$ $-$ realized by one of the relations $``\geq"$ or
$``\leq"$.

Let
${\mathcal{P}}=\\{\max,\min\\}\times\\{\textnormal{bases},\textnormal{IS}\\}\times\\{\leq,\geq\\}$
be the set of parameters for MOL problems. Based on the set of parameters
${\mathcal{P}}$, we define for every triplet a problem in the MOL family. For
$P\in{\mathcal{P}}$ where
$P=\left(\textnormal{opt},{\mathcal{F}},\triangleleft\right)$, define the
$P$-matroid optimization with a linear constraint ($P$-MOL) problem as
follows. An instance is a tuple $I=(E,{\mathcal{I}},v,w,L)$ such that
${\mathcal{M}}=(E,{\mathcal{I}})$ is a matroid,
$v:E\rightarrow\mathbb{R}_{\geq 0}$ is the objective function,
$w:E\rightarrow\mathbb{R}_{\geq 0}$ is a weight function, and
$L\in\mathbb{R}_{\geq 0}$ is a bound for the linear constraint. A solution of
$I$ is $S\subseteq E$ which satisfies the matroid feasibility constraint
$S\in{\mathcal{F}}({\mathcal{M}})$ and the linear constraint
$w(S)\triangleleft L$. The goal is to optimize (i.e., maximize or minimize)
the value $v(S)$. Thus, we can formulate a P-MOL optimization problem as

$\textnormal{opt}~{}v(S)\text{ s.t.
}S\in{\mathcal{F}}({\mathcal{M}}),~{}w(S)\triangleleft L.$ (1)

Observe that $(\max,\textnormal{IS},\leq)$-MOL is the BM problem. That is,
given a BM instance (equivalently, $(\max,\textnormal{IS},\leq)$-MOL instance)
$I=(E,{\mathcal{I}},v,w,L)$, the goal is to find an independent set
$S\in{\mathcal{I}}$ of maximum total value $v(S)$ such that $w(S)\leq L$.
Other notable examples for MOL problems are constrained minimum basis of a
matroid (CMB) [25], which can be cast as $(\min,\textnormal{bases},\leq)$-MOL,
and knapsack cover with matroid constraint (KCM) [8] formalized by
$(\min,\textnormal{IS},\geq)$-MOL.444CMB, KCM, and other MOL problems may not
have a solution; however, we can decide in polynomial time if a solution
exists, and our definition of approximation algorithms captures instances with
no solution.

We note that (1) does not refer to the representation of the instance $I$. We
consider two possible representations. For any $P\in{\mathcal{P}}$, in an
instance $(E,{\mathcal{I}},v,w,L)$ of oracle $P$-MOL, the arguments $E,v,w,L$
are given as the input, and the independent sets ${\mathcal{I}}$ are accessed
via a membership oracle, which determines whether a given set $S\subseteq E$
belongs to ${\mathcal{I}}$ in a single query. Thus, the independent sets are
not considered in the encoding size of the instance. The term running time for
problems involving oracles refers to the sum of the number of queries to the
oracle and the number of basic operations. Previous works on MOL problems
often consider membership oracles [12, 2, 8, 19, 18]. As hardness with oracles
does not necessarily imply hardness in non-oracle models (see, e.g., [6, 9]),
in Section 4 we show lower bounds for variants of MOL problems in which the
independent sets are encoded as part of the input.

Clearly, the problem $(\min,\textnormal{IS},\leq)$-MOL is trivial since the
empty set achieves the optimal objective value. However, for any other
$P\in{\mathcal{P}}$, solving the $P$-MOL problem is challenging. The non-
trivial MOL problems are all the MOL problems excluding
$(\min,\textnormal{IS},\leq)$-MOL. That is, $P$-MOL is non-trivial if
$P\in{\mathcal{Q}}$ where
${\mathcal{Q}}={\mathcal{P}}\setminus\\{(\min,\textnormal{IS},\leq)\\}$.
Observe that non-trivial MOL problems are NP-hard (e.g., $0/1$-knapsack is a
special case of $(\max,\textnormal{IS},\leq)$-MOL); however, all previously
studied MOL problems admit approximation schemes.

For certain special cases of MOL problems, e.g., BM with simple matroid
constraints, the existence of a Fully PTAS is known for decades [37, 7].
However, for MOL problems with arbitrary matroid constraints, the best known
results are Efficient PTAS. While matroids form an important generalization of
well known basic constraints, the complexity of the corresponding MOL problems
remained open. Specifically, prior to this work, the existence of a MOL
problem which does not admit a Fully PTAS was open.

Our main result is that none of the (non-trivial) oracle matroid optimization
problem with a linear constraint admits a Fully PTAS, even if randomization is
allowed. This unconditioned hardness result is established by deriving a lower
bound on the minimum number of queries to the membership oracle.

######  Theorem 1.1.

For every $P\in{\mathcal{Q}}$ there is no randomized Fully PTAS for oracle
$P$-MOL.

Problem |  Previous Results |  This Paper
---|---|---
Budgeted Matroid Independent Set |  Efficient PTAS [19] |  No Fully PTAS
Budgeted Matroid Intersection |  Efficient PTAS [18] |  No Fully PTAS
Constrained Minimum Basis of Matroid |  Efficient PTAS [25] |  No Fully PTAS
Knapsack Cover with a Matroid |  PTAS [8] |  No Fully PTAS
Table 1: Implications of our results for previously studied MOL problems. All
of our bounds hold for randomized algorithms.

Theorem 1.1 conclusively distinguishes MOL problems with arbitrary matroids,
such as BM, from special cases with simpler matroid constraints. Furthermore,
it shows that existing Efficient PTAS [25, 19, 18] for MOL problems on general
matroids are the best possible. Notable implications of our results are given
in Table 1, and consequences of our lower bounds for a set of previously
studied problems [5, 25, 2, 12, 24, 8, 19, 18, 17] are given in Section 1.3.
By resolving the complexity status of MOL problems on general matroids, our
results promote future research to design (or rule out) Fully PTAS for MOL
problems on restricted matroid classes (see Section 5).

To prove Theorem 1.1, we turn our attention to the following problem.

######  Definition 1.2.

An instance of Exact Matroid Basis (EMB) is $I=(E,{\mathcal{I}},c,T)$, where
$(E,{\mathcal{I}})$ is a matroid, $c:E\rightarrow\mathbb{N}$ is a weight
function, and $T\in\mathbb{N}$ is a target value. A solution is a basis $S$ of
$(E,{\mathcal{I}})$ such that $c(S)=T$. The goal is to decide if there is a
solution.

Similar to MOL problems, EMB does not specify the input. In an instance
$(E,{\mathcal{I}},c,T)$ of oracle-EMB, $E,c,T$ are explicitly given, and the
independent sets ${\mathcal{I}}$ are accessed via a membership oracle. An
instance $I$ of a decision problem ${\mathcal{D}}$ is a “yes”-instance if the
correct answer for $I$ is “yes”; otherwise, $I$ is a “no”-instance. We say
that ${\mathcal{A}}$ is a randomized algorithm for a decision problem
${\mathcal{D}}$ if, given a “yes”-instance $I$ of ${\mathcal{D}}$,
${\mathcal{A}}$ returns “yes” with probability at least $\frac{1}{2}$; for a
“no”-instance, ${\mathcal{A}}$ returns “no” with probability $1$. The next
result rules out a pseudo-polynomial time algorithm for oracle-EMB, thus
distinguishing the problem from the special cases of $k$-subset sum and EMB on
linear matroids, which admit a pseudo-polynomial time algorithm [5].

######  Theorem 1.3.

There is no randomized algorithm for oracle-EMB that for any oracle-EMB
instance $I=(E,{\mathcal{I}},c,T)$, where $n=|E|+1$ and $m=c(E)+1$, runs in
time $\left(n\cdot(T+2)\cdot m\right)^{O(1)}$.

###  1.2 Technical Contribution

We derive our results by introducing $\Pi$-matroids. This new family of
matroids carefully exploits a simple weight function to define a matroid that
successfully hides a specific property $\Pi$ within its independent sets (see
Section 2). Using $\Pi$-matroids, we define oracle-EMB instances whose
solutions must satisfy the property $\Pi$. This shows the unconditional
hardness of oracle-EMB, as $\Pi$ can be discovered only via an exponential
number of queries to the membership oracle. Our hardness results for MOL
problems (as stated in Theorem 1.1) are derived via reduction from oracle-EMB.

Despite the abundance of lower bounds for matroid problems [32, 27, 28, 38],
as well as for knapsack problems [10, 29, 14, 3], we are not aware of lower
bounds that leverage the interaction between the matroid constraint and the
additional linear constraint required for deriving our new lower bound for
EMB, and consequently for MOL problems. Indeed, if the matroid constraint is
removed from (1) (equivalently, ${\mathcal{F}}({\mathcal{M}})=2^{E}$), MOL
problems become variants of classic $0/1$-knapsack, which admits a Fully PTAS.
Alternatively, if the linear constraint imposed by $w,L$ is removed, then we
have the polynomially solvable maximum/minimum weight matroid independent set
problem. This distinguishes our construction from existing lower bounds for
matroid problems. $\Pi$-matroids may be useful for deriving lower bounds for
other problems (see Section 5).

Our unconditional lower bounds apply in the oracle model, where the
independent sets of the given matroid can be accessed only via a membership
oracle. One may question the validity of the bounds for variants of the
problems where the matroid is encoded as part of the input. Indeed, in some
scenarios, the use of oracles makes problems harder [6, 9]. Thus, we
complement our results by showing that the same lower bounds hold under the
standard complexity assumption $\textnormal{P}\neq\textnormal{NP}$, even if
the matroid is encoded as part of the instance and membership can be decided
in polynomial time. We accomplish this by designing the family of SAT-matroids
$-$ a counterpart of the $\Pi$-matroid family whose members can be efficiently
encoded. This construction can be used to obtain hardness results for other
matroid problems in non-oracle models, based on existing analogous lower
bounds in the oracle model (e.g., [27]). We elaborate on that in Section 4.

###  1.3 Implications of Our Results and Prior Work

Below we describe in further detail the implications of our results, and
discuss previous work on MOL problems. In the following problems, general
matroids are assumed to be accessed via membership oracles.

#### Exact Matroid Basis (EMB):

This is a generalization of the $k$-subset sum problem (where
$(E,{\mathcal{I}})$ is a uniform matroid).555In a uniform matroid,
${\mathcal{I}}=\\{S\subseteq E~{}|~{}|S|\leq k\\}$. Thus, EMB is unlikely to
be solvable in polynomial time. Instead, we seek a pseudo-polynomial time
algorithm whose running time has polynomial dependence on the encoding size of
the instance and the target value $T$. Indeed, the special case of EMB in
which the matroid is representable (or, linear) admits such a pseudo-
polynomial time algorithm [5]. Since the 1990s, it has been an open question
whether the result of Camerini et al. [5] can be extended to general matroids.
Theorem 1.3 resolves this question, ruling out the existence of a pseudo-
polynomial time algorithm for EMB.

#### Budgeted Matroid Independent Set (BM):

This problem is cast as $(\max,\textnormal{IS},\leq)$-MOL. BM is a natural
generalization of the classic $0/1$-knapsack problem, for which a Fully PTAS
has been known since the 1970s [31]. As mentioned above, a Fully PTAS is known
also for other special cases of BM. A PTAS for BM was first given in [2] as a
special case of budgeted matroid intersection (BMI). In this generalization of
BM, we are given two matroids $(E,{\mathcal{I}}_{1})$ and
$(E,{\mathcal{I}}_{2})$, and a solution has to be an independent set of both
matroids. A PTAS for BM also follows from the results of [24, 12] which
present PTASs for multi-budgeted variants of BM. An Efficient PTAS for BM was
recently given in [19] and for BMI in [18]. The existence of a Fully PTAS for
BM was posed as a central open question in [2, 19, 18]. We answer this
question negatively, as formalized in Theorem 1.1, giving a tight lower bound
for BM and BMI.

#### Constrained Minimum Basis of a Matroid (CMB):

This problem can be cast as the matroid optimization problem
$(\min,\textnormal{bases},\leq)$-MOL. The constrained minimum spanning tree
(CST) problem is the special case of CMB in which the matroid
$(E,{\mathcal{I}})$ is graphical [35, 1, 25, 26], namely, there is a graph
$G=(V,E)$ such that the independent sets ${\mathcal{I}}$ are cycle-free
subsets of edges in $G$. A PTAS for CST was given by Ravi and Goemans [35].
This result was improved to an Efficient PTAS by Hassin and Levin [25]. A
bicriteria FPTAS, which violates the budget constraint by a factor of
$(1+{\varepsilon})$, was presented in [26]. The authors of [25] mention that
their result actually gives an Efficient PTAS for CMB. The existence of a
Fully PTAS for CMB remained an open question. Theorem 1.1 shows that the
Efficient PTAS for CMB cannot be improved.

#### Knapsack Cover with a Matroid (KCM):

As a final implication, Theorem 1.1 rules out the existence of a Fully PTAS
for a coverage variant of $0/1$-knapsack, formulated as
$(\min,\textnormal{IS},\geq)$-MOL. In [8], Chakaravarthy et al. presented a
PTAS for KCM using integrality properties of a linear programming formulation
of KCM. Moreover, for the special case of KCM with a partition matroid, they
give a Fully PTAS based on dynamic programming. The existence of a Fully PTAS
for KCM on a general matroid was posed in [8] as an open question. Theorem 1.1
answers this question negatively. Our initial study indicates that an
Efficient PTAS for KCM can potentially be obtained by adapting the approach of
Hassin and Levin [25] to the setting of KCM. This suggests that our lower
bound cannot be strengthened.

#### Organization:

In Section 2 we introduce the $\Pi$-matroid family and give the proof of
Theorem 1.3. In Section 3 we prove Theorem 1.1, and in Section 4 we show that
similar lower bounds hold in the standard computational model. We conclude in
Section 5 with a summary and directions for future work.

##  2 The Hardness of oracle exact matroid basis

In this section, we prove Theorem 1.3. We use in the proof the family of
$\Pi$-matroids. A member in the $\Pi$-matroid family is given by four
arguments: $n,k,\alpha\in\mathbb{N}_{>0}$, and $\Pi\subseteq 2^{[n]}$. For any
$m\in\mathbb{N}$, let $[m]=\\{1,\ldots,m\\}$. The first argument,
$n\in\mathbb{N}_{>0}$, is the number of elements, and the ground set is $[n]$.
The second argument, $k\in[n]$, is the rank of the matroid. The third
argument, $\alpha\in\mathbb{N}_{>0}$, is a target value, that is usually equal
to $\textnormal{{sum}}(S)$ for some $S\subseteq[n]$, where
$\textnormal{{sum}}(S)=\sum_{i\in S}i$. The last argument is a family of
subsets $\Pi\subseteq 2^{[n]}$, where $2^{[n]}=2^{\\{1,\ldots,n\\}}$.

The set $\Pi$ is called the secret family because finding $S\in\Pi$ is
possible only via repeated queries to the membership oracle of the matroid.
Since $\Pi$ can have an arbitrary structure, this may require exhaustive
enumeration.

######  Definition 2.1.

Let $n,k,\alpha\in\mathbb{N}_{>0}$. For some $\Pi\subseteq 2^{[n]}$, define
the $\Pi$-matroid on $n,k$, and $\alpha$ as
$M_{n,k,\alpha}(\Pi)=([n],{\mathcal{I}}_{n,k,\alpha}(\Pi))$, where

${\mathcal{I}}_{n,k,\alpha}(\Pi)=\mathcal{J}_{n,k}\cup\mathcal{K}_{n,k,\alpha}\cup\mathcal{L}_{n,k,\alpha}(\Pi)$

and $\mathcal{J}_{n,k},\mathcal{K}_{n,k,\alpha},\mathcal{L}_{n,k,\alpha}(\Pi)$
are defined as follows.

$\displaystyle\mathcal{J}_{n,k}~{}~{}~{}~{}~{}~{}={}$
$\displaystyle\big{\\{}S\subseteq[n]~{}\big{|}~{}|S|<k\big{\\}}$ (2)
$\displaystyle\mathcal{K}_{n,k,\alpha}~{}~{}~{}~{}={}$
$\displaystyle\big{\\{}S\subseteq[n]~{}\big{|}~{}|S|=k,\textnormal{{sum}}(S)\neq\alpha\big{\\}}$
$\displaystyle\mathcal{L}_{n,k,\alpha}(\Pi)={}$
$\displaystyle\big{\\{}S\subseteq[n]~{}\big{|}~{}|S|=k,\textnormal{{sum}}(S)=\alpha,S\in\Pi\big{\\}}.$

$\bf{\color[rgb]{0,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,.5,.5}1}$$\bf{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}2}$$\bf{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}3}$$\bf{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}4}$$~{}\Pi=\\{\textnormal{independent
sets of }G\\}$A graph
$G$$\mathcal{J}_{4,2}=\\{\emptyset,\\{$1$\\},\\{$2$\\},\\{$3$\\},\\{$4$\\}\\},~{}~{}\mathcal{K}_{4,2,5}=\\{\\{$2,4$\\},\\{$2,1$\\},\\{$4,3$\\},\\{$3,1$\\}\\},~{}~{}\mathcal{L}_{4,2,5}(\Pi)=\\{\\{$2,3$\\}\\}$
Figure 1:  The independent sets of the $\Pi$-matroid $M_{n,k,\alpha}(\Pi)$,
with parameters $n=4$, $k=2$, and $\alpha=5$. The secret family $\Pi$ contains
all independent sets in the graph $G$, where $\\{2,3\\}$ is the only
independent set in $G$ with $k$ elements.

In words, $\mathcal{J}_{n,k}$ contains all subsets of strictly less than $k$
elements; $\mathcal{K}_{n,k,\alpha}$ contains all subsets of cardinality $k$
whose total sum is not $\alpha$; finally, $\mathcal{L}_{n,k,\alpha}(\Pi)$
contains all subsets of cardinality $k$ and total sum $\alpha$ which also
belong to $\Pi$. See Figure 1 for an example of a member of the $\Pi$-matroid
family. Using a simple argument, we show that the set system in Definition 2.1
is indeed a matroid. For the sets ${\mathcal{I}}_{n,k,\alpha}(\Pi)$,
$\mathcal{J}_{n,k}$, $\mathcal{K}_{n,k,\alpha}$ and
$\mathcal{L}_{n,k,\alpha}(\Pi)$ defined in Definition 2.1, we often omit the
subscripts ${n,k,\alpha}$ and ${n,k}$ when the values of $n,k,\alpha$ are
known by context. For simplicity, for any set $A$ and an element $a$, let
$A+a$, $A-a$ be $A\cup\\{a\\}$ and $A\setminus\\{a\\}$, respectively.

######  Lemma 2.2.

For every $n,k,\alpha\in\mathbb{N}_{>0}$, and $\Pi\subseteq 2^{[n]}$ it holds
that $M_{n,k,\alpha}(\Pi)$ is a matroid.

###### Proof.

We first note that $\emptyset\in\mathcal{J}$ since $0<k$; therefore,
$\emptyset\in{\mathcal{I}}(\Pi)$. For the hereditary property, let
$A\in{\mathcal{I}}(\Pi)$. For all $B\subset A$ it holds that $|B|<k$; thus,
$B\in\mathcal{J}$ and it follows that $B\in{\mathcal{I}}(\Pi)$. For the
exchange property, let $A,B\in{\mathcal{I}}(\Pi)$ such that $|A|>|B|$. We
consider the following cases.

  1. 1.

$|B|<k-1$. Then, for all $e\in A\setminus B$ it holds that $|B+e|<k-1+1=k$;
thus, $B+e\in{\mathcal{J}}$ and it follows that $B+e\in{\mathcal{I}}(\Pi)$.
Note that there is such $e\in A\setminus B$ because $|A|>|B|$.

  2. 2.

$|B|=k-1$ and $|A|=k$. We consider two subcases.

    1. (a)

$B\subseteq A$. Then, as $|A|>|B|$ there is $e\in A\setminus B$; thus, $B+e=A$
(because $|B|=k-1$ and $|A|=k$). As $A\in{\mathcal{I}}(\Pi)$, it follows that
$B+e\in{\mathcal{I}}(\Pi)$.

    2. (b)

$B\not\subseteq A$. Then, as $|B|=k-1$ and $|A|=k$ it follows that $|B\cap
A|<|B|=k-1$; thus, $|A\setminus B|=|A|-|A\cap B|>k-(k-1)=1$. Therefore, there
are $e,f\in A\setminus B$ such that $e\neq f$. It follows that there is
$g\in\\{e,f\\}$ such that
$\textnormal{{sum}}(B+g)=\textnormal{{sum}}(B)+g\neq\alpha$. We conclude from
(2) that $B+g\in\mathcal{K}$, implying that $B+g\in{\mathcal{I}}(\Pi)$.

∎

Observe that $\mathcal{K}_{n,k,\alpha}\cup\mathcal{L}_{n,k,\alpha}(\Pi)$ is
the set of bases of the matroid. Moreover, for any arguments $n$, $k$,
$\alpha$ and $\Pi$, the cardinality of every dependent set $S\in
2^{[n]}\setminus{\mathcal{I}}_{n,k,\alpha}(\Pi)$ is at least the rank of the
$\Pi$-matroid $M_{n,k,\alpha}(\Pi)=([n],{\mathcal{I}}_{n,k,\alpha}(\Pi))$.
Such matroids are known as paving matroids (see, e.g., [33, 34]). Using
$\Pi$-matroids, we define the following collection of oracle-EMB instances. In
these instances, the matroid is a $\Pi$-matroid, where $\Pi$ is some unknown
fixed family of subsets of the ground set.

######  Definition 2.3.

For every $n,k,\alpha\in\mathbb{N}_{>0}$, $\Pi\subseteq 2^{[n]}$ define the
induced oracle-EMB instance of $n,k,\alpha,\Pi$, denoted
$I_{n,k,\alpha}(\Pi)$, as follows. Let
$\textnormal{{id}}_{n}:[n]\rightarrow[n]$, where
$\textnormal{{id}}_{n}(i)=i~{}\forall i\in[n]$. Then,
$I_{n,k,\alpha}(\Pi)=([n],{\mathcal{I}}_{n,k,\alpha}(\Pi),\textnormal{{id}}_{n},\alpha)$.

Observe that the above is indeed an oracle-EMB instance if the independent
sets of the given matroid are accessible via a membership oracle. The
following is an easy consequence of Definition 2.3.

######  Observation 2.4.

For every $n,k,\alpha\in\mathbb{N}_{>0}$ and $\Pi\subseteq 2^{[n]}$, it holds
that $I_{n,k,\alpha}(\Pi)$ is an oracle-EMB ”yes”-instance if and only if
there is $S\in\Pi$ such that $|S|=k$ and
$\textnormal{{sum}}(S)=\textnormal{{id}}_{n}(S)=\alpha$.

By 2.4, an algorithm that finds an independent set of
$\mathcal{M}_{n,k,\alpha}(\Pi)$ satisfying $|S|=k$ and
$\textnormal{{sum}}(S)=\alpha$, in fact outputs a subset $S\in\Pi$. As the
input for an induced oracle-EMB instance $I_{n,k,\alpha}(\Pi)$ does not
contain an explicit encoding of $\Pi$, finding $S\in\Pi$ requires a sequence
of queries to the membership oracle of $M_{n,k,\alpha}(\Pi)$. Roughly
speaking, to decide $I_{n,k,\alpha}(\Pi)$, an algorithm for oracle-EMB must
iterate over all (exponentially many) subsets $S\subseteq[n]$ such that
$|S|=k$ and $\textnormal{{sum}}(S)=\alpha$. This is the intuition behind the
proof of the next result.

$\bf{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}I}$$1$no$2$yes$3$no$\ldots$$|Q(b)|$no$\bf{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}S\notin
Q(b)},~{}~{}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}S\notin{\mathcal{I}}(\Pi_{\emptyset})}$$\bf{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}I_{S}}$$1$no$2$yes$3$no$\ldots$$|Q(b)|$no$\bf{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}S\notin
Q(b)},~{}~{}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}S\in{\mathcal{I}}(\Pi_{S})}$
Figure 2:  An illustration of the proof of Theorem 1.3. The figure presents
the sequences of queries to the membership oracles by the algorithm on the
instances $I$ and $I_{S}$ for a string of bits $b$, such that $S\notin Q(b)$.
The label ”yes” (”no”) indicates that the queried set is (not) independent in
the matroid. The only query that distinguishes between $I$ and $I_{S}$ is on
the set $S$, which is not queried; thus, the algorithm returns the same output
for $I$ and $I_{S}$.

See 1.3

###### Proof.

Assume towards contradiction that there exist a constant $d\in\mathbb{N}$ and
a randomized algorithm ${\mathcal{A}}$ that decides every oracle-EMB instance
$(E,{\mathcal{I}},c,T)$ in time $\left((T+2)\cdot n\cdot m\right)^{d}$, where
$n=|E|+1$ and $m=c(E)+1$. For every $n,k,\alpha\in\mathbb{N}_{>0}$, consider
the set of all subsets of $[n]$ with cardinality $k$ and sum $\alpha$:

$\mathcal{F}_{n,k,\alpha}=\big{\\{}S\subseteq[n]~{}\big{|}~{}|S|=k,\textnormal{{sum}}(S)=\alpha\big{\\}}.$

To reach a contradiction, we construct an induced oracle-EMB instance on which
${\mathcal{A}}$ does not compute the proper output with sufficiently high
probability. The parameters of the instance are extracted from the following
combinatorial claim.

######  Claim 2.5.

There are $\tilde{n}\in\mathbb{N}_{>0}$, $\tilde{k}\in\left[\tilde{n}\right]$,
and $\tilde{\alpha}\in\left[\tilde{n}^{2}\right]$ such that
$|\mathcal{F}_{\tilde{n},\tilde{k},\tilde{\alpha}}|>2\cdot\left(12\cdot\tilde{n}^{5}\right)^{d}$.

###### Proof.

Since $d$ is a constant, there is $\tilde{n}\in\mathbb{N}_{>0}$ such that

$\left(12\cdot\tilde{n}^{5}\right)^{d}<\frac{2^{\tilde{n}}-1}{2\cdot\tilde{n}^{3}}.$
(3)

Fix $\tilde{n}\in\mathbb{N}_{>0}$ satisfying (3). Recall that
$\sum_{k\in\\{0,1,\ldots,\tilde{n}\\}}{\tilde{n}\choose k}=2^{\tilde{n}}$ from
a basic property of the Pascal triangle; therefore,
$\sum_{k\in\\{1,\ldots,\tilde{n}\\}}{\tilde{n}\choose k}=2^{\tilde{n}}-1$.
Thus, there is $\tilde{k}\in\\{1,\ldots,\tilde{n}\\}$, such that

${\tilde{n}\choose\tilde{k}}\geq\frac{2^{\tilde{n}}-1}{\tilde{n}}.$ (4)

Fix $\tilde{k}\in\left[\tilde{n}\right]$ satisfying (4). Observe that for each
$S\in 2^{[\tilde{n}]}$ satisfying $|S|=\tilde{k}>0$, it holds that
$1\leq\textnormal{{sum}}(S)\leq|S|\cdot\max_{i\in[\tilde{n}]}i=\tilde{n}^{2}$.
Thus, there are $\tilde{n}^{2}$ possibilities for
$\alpha\in\left[\tilde{n}^{2}\right]$ satisfying
$\alpha=\textnormal{{sum}}(S)$, for some $S\in 2^{[\tilde{n}]}$ such that
$|S|=\tilde{k}$. Moreover, there are ${\tilde{n}\choose\tilde{k}}$ subsets of
$[\tilde{n}]$ of cardinality $\tilde{k}$. By the pigeonhole principle, there
is $\tilde{\alpha}\in\left[\tilde{n}^{2}\right]$ such that
$|\mathcal{F}_{\tilde{n},\tilde{k},\tilde{\alpha}}|\geq\frac{{\tilde{n}\choose\tilde{k}}}{\tilde{n}^{2}}$.
Thus,

$|\mathcal{F}_{\tilde{n},\tilde{k},\tilde{\alpha}}|\geq\frac{{\tilde{n}\choose\tilde{k}}}{\tilde{n}^{2}}\geq\frac{2^{\tilde{n}}-1}{\tilde{n}\cdot\tilde{n}^{2}}>2\cdot\left(12\cdot\tilde{n}^{5}\right)^{d}.$

The second inequality follows from (4), and the third inequality holds by (3).
$\square$

Let $\tilde{n}\in\mathbb{N}_{>0}$, $\tilde{k}\in\left[\tilde{n}\right]$, and
$\tilde{\alpha}\in\left[\tilde{n}^{2}\right]$ satisfying the conditions of
Claim 2.5. Define $t$ to be the maximum running time of ${\mathcal{A}}$ on an
induced EMB instance $I_{\tilde{n},\tilde{k},\tilde{\alpha}}(\Pi)$ over all
$\Pi\in 2^{\left[\tilde{n}\right]}$.

######  Claim 2.6.

$t\leq\left(12\cdot\tilde{n}^{5}\right)^{d}$.

###### Proof.

Let $T=\tilde{\alpha}$, $n=\tilde{n}+1$, and
$m=\textsf{id}_{\tilde{n}}(\left[\tilde{n}\right])+1$. By the running time
guarantee of ${\mathcal{A}}$, it follows that $t\leq\left(n\cdot(T+2)\cdot
m\right)^{d}$. It remains to bound $n\cdot(T+2)\cdot m$. Since
$\textsf{id}_{\tilde{n}}(\left[\tilde{n}\right])=\textsf{sum}(\left[\tilde{n}\right])$
and $\tilde{\alpha}\leq\tilde{n}^{2}$,

$n\cdot(T+2)\cdot
m\leq\left(\tilde{n}+1\right)\cdot\left(\tilde{n}^{2}+2\right)\left(\textsf{sum}(\left[\tilde{n}\right])+1\right)\leq
2\tilde{n}\cdot
3\tilde{n}^{2}\cdot\left(\frac{\tilde{n}\cdot(\tilde{n}+1)}{2}+1\right)\leq
12\cdot\tilde{n}^{5}.$

The second inequality follows from the sum of the terms of an arithmetic
sequence. By the above and the running time guarantee of ${\mathcal{A}}$, it
follows that $t\leq\left(n\cdot(T+2)\cdot
m\right)^{d}\leq\left(12\cdot\tilde{n}^{5}\right)^{d}$. $\square$

Given an induced oracle-EMB instance
$I_{\tilde{n},\tilde{k},\tilde{\alpha}}(\Pi)$, for some
$\Pi\subseteq\left[\tilde{n}\right]$, the randomized algorithm ${\mathcal{A}}$
produces a random string of bits $\bar{b}\in\\{0,1\\}^{t}$ and performs a
sequence of queries to the membership oracle of
$M_{\tilde{n},\tilde{k},\tilde{\alpha}}$, based on
$\bar{b},\tilde{n},\tilde{k},\tilde{\alpha}$, and the results of the previous
queries; then, the algorithm decides the given instance based on the queries.

Let $\Pi_{\emptyset}=\emptyset$, and consider the induced oracle-EMB instance
$I=I_{\tilde{n},\tilde{k},\tilde{\alpha}}(\Pi_{\emptyset})$. Given a string of
bits $b\in\\{0,1\\}^{t}$, let $Q(b)\subseteq 2^{[\tilde{n}]}$ be the set of
all subsets $S\subseteq[\tilde{n}]$ queried by ${\mathcal{A}}$ on the instance
$I$ and the bit-string $b$ (on the membership oracle of
$M_{\tilde{n},\tilde{k},\tilde{\alpha}}(\Pi_{\emptyset})$). For clarity, we
use $\bar{b}$ for a random string, and $b$ for a realization of $\bar{b}$ to a
specific string. Note that $Q(b)$ is a set, since the algorithm is
deterministic for every $b\in\\{0,1\\}^{t}$; conversely, $Q(\bar{b})$ is a
random set for a random string $\bar{b}\in\\{0,1\\}^{t}$. As the running time
of ${\mathcal{A}}$ on $I$ is bounded by $t$, it holds that $|Q(b)|\leq t$ for
every $b\in\\{0,1\\}^{t}$. Let

$R(I)=\left\\{S\in\mathcal{F}_{\tilde{n},\tilde{k},\tilde{\alpha}}~{}\bigg{|}~{}\Pr\left(S\in
Q(\bar{b})\right)\geq\frac{1}{2}\right\\}$

be all sets in $\mathcal{F}_{\tilde{n},\tilde{k},\tilde{\alpha}}$ that are
queried by ${\mathcal{A}}$ with probability at least $\frac{1}{2}$.

######  Claim 2.7.

$|R(I)|<|\mathcal{F}_{\tilde{n},\tilde{k},\tilde{\alpha}}|$.

###### Proof.

By the definition of $R(I)$, it holds that

$\displaystyle|R(I)|={}$
$\displaystyle\left|\left\\{S\in\mathcal{F}_{\tilde{n},\tilde{k},\tilde{\alpha}}~{}\bigg{|}~{}\Pr\left(S\in
Q(\bar{b})\right)\geq\frac{1}{2}\right\\}\right|$ $\displaystyle\leq{}$
$\displaystyle
2\cdot\sum_{S\in\mathcal{F}_{\tilde{n},\tilde{k},\tilde{\alpha}}}\Pr\left(S\in
Q(\bar{b})\right)$ $\displaystyle={}$ $\displaystyle
2\cdot\sum_{S\in\mathcal{F}_{\tilde{n},\tilde{k},\tilde{\alpha}}~{}}\sum_{b\in\\{0,1\\}^{t}}\Pr\left(S\in
Q(b)\right)\cdot\Pr(\bar{b}=b)$

Thus, by changing the order of summation, we have

$\displaystyle|R(I)|\leq
2\cdot\sum_{b\in\\{0,1\\}^{t}~{}}\Pr(\bar{b}=b)\cdot\sum_{S\in\mathcal{F}_{\tilde{n},\tilde{k},\tilde{\alpha}}}\Pr\left(S\in
Q(b)\right)\leq 2\cdot\sum_{b\in\\{0,1\\}^{t}~{}}\Pr(\bar{b}=b)\cdot|Q(b)|.$

Since $\left|Q(b)\right|\leq t$ for all $b\in\\{0,1\\}^{t}$, by the above we
have

$|R(I)|\leq 2t\cdot\sum_{b\in\\{0,1\\}^{t}~{}}\Pr(\bar{b}=b)=2\cdot t\leq
2\cdot\left(12\cdot\tilde{n}^{5}\right)^{d}<|\mathcal{F}_{\tilde{n},\tilde{k},\tilde{\alpha}}|.$

The second inequality follows from Claim 2.6. The last inequality holds by
Claim 2.5. $\square$

By Claim 2.7, there exists $S\in
F_{\tilde{n},\tilde{k},\tilde{\alpha}}\setminus R(I)$. Consider the induced
oracle-EMB instance $I_{S}=I_{\tilde{n},\tilde{k},\tilde{\alpha}}(\Pi_{S})$
where $\Pi_{S}=\\{S\\}$, and let $B=\\{b\in\\{0,1\\}^{t}~{}|~{}S\notin
Q(b)\\}$ be all strings for which $S$ is not queried by ${\mathcal{A}}$ on the
instance $I$ . Observe that for all $b\in B$ it holds that the answers to all
queries for $T\in Q(b)$ are the same for both oracles (of
$M_{\tilde{n},\tilde{k},\tilde{\alpha}}(\Pi_{\emptyset})$ and
$M_{\tilde{n},\tilde{k},\tilde{\alpha}}(\Pi_{S})$). Moreover, the decision on
which set to query next depends only on
$b,\tilde{n},\tilde{k},\tilde{\alpha}$, and the answers to previous queries.

Hence, for all $b\in B$, the executions of ${\mathcal{A}}$ on the instances
$I$ and $I_{S}$ are identical. Since $\Pi_{\emptyset}=\emptyset$, by 2.4, $I$
is a “no”-instance for oracle-EMB; thus, ${\mathcal{A}}$ returns that $I_{S}$
is a “no”-instance for every $b\in B$. However, since
$\textsf{id}_{n}(S)=\textsf{sum}(S)=\alpha$, $|S|=k$, and $S\in\Pi_{S}$, it
follows that $I_{S}$ is a “yes”-instance by 2.4. Therefore, ${\mathcal{A}}$
does not decide $I_{S}$ correctly for all $b\in B$. We give an illustration in
Figure 2. Since $S\notin R(I)$, it holds that $\Pr\left(\bar{b}\in
B\right)=\Pr\left(S\notin Q(\bar{b})\right)>\frac{1}{2}$; thus, with
probability greater than $\frac{1}{2}$, ${\mathcal{A}}$ does not decide
correctly the instance $I_{S}$. A contradiction to the correctness of
${\mathcal{A}}$ as a randomized algorithm for oracle-EMB. The statement of the
theorem follows. ∎

##  3 Hardness of Matroid Optimization with a Linear Constraint

In this section we use Theorem 1.3 to prove Theorem 1.1. We apply the
following reductions from EMB to MOL problems. Recall that
${\mathcal{Q}}={\mathcal{P}}\setminus\\{(\min,\textnormal{IS},\leq)\\}$ is the
set of parameters for non-trivial MOL problems. Given a $P$-MOL problem for
some $P\in{\mathcal{Q}}$, and an EMB instance $I$, the reduction returns an
instance $R_{P}(I)$ of the $P$-MOL problem. Note that the reduction is purely
mathematical, and does not specify the encoding of the instance. This will be
useful for obtaining our hardness results in non-oracle computational models
(see Section 4).

Given
$(\textnormal{opt},{\mathcal{F}},\triangleleft),(\textnormal{opt}^{\prime},{\mathcal{F}}^{\prime},\triangleleft^{\prime})\in{\mathcal{Q}}$,
we use the notation $(\textnormal{opt}\textnormal{ is
}\textnormal{opt}^{\prime})$, $({\mathcal{F}}\textnormal{ is
}{\mathcal{F}}^{\prime})$, $(\triangleleft\textnormal{ is
}\triangleleft^{\prime})$ to denote the boolean expressions of equality
between parameters of a MOL problem. For example,
$(\textnormal{opt}\textnormal{ is }\textnormal{opt}^{\prime})$ is true if and
only if either $\textnormal{opt},\textnormal{opt}^{\prime}$ are both $\max$,
or $\textnormal{opt},\textnormal{opt}^{\prime}$ are both $\min$.

######  Definition 3.1.

Given an EMB instance $I=(E,{\mathcal{I}},c,T)$ and $P\in{\mathcal{Q}}$ where
$P=(\textnormal{opt},{\mathcal{F}},\triangleleft)$, define the reduced $P$-MOL
instance of $I$, denoted by
$R_{P}(I)=(E,{\mathcal{I}},v_{I},w_{I,P},L_{I,P})$, as follows.

  1. 1.

Define the auxiliary variable

$\displaystyle d(P)=$ $\displaystyle\begin{cases}0&~{}~{}\textnormal{if
}\bigg{(}(\textnormal{opt}\textnormal{ is }\max)\textnormal{ and
}(\triangleleft\textnormal{ is}\leq)\bigg{)}\textnormal{ or
}\bigg{(}(\textnormal{opt}\textnormal{ is }\min)\textnormal{ and
}(\triangleleft\textnormal{ is}\geq)\bigg{)}\\\
1&~{}~{}\textnormal{otherwise.}\end{cases}$

For example, if $P=(\max,\textnormal{IS},\leq)$ then $d(P)=0$, and if
$P^{\prime}=(\max,\textnormal{IS},\geq)$ then $d(P^{\prime})=1$.

  2. 2.

Let $H_{I}=2\cdot\max\\{1,c(E)\\}$.

  3. 3.

For all $e\in E$ let $v_{I}(e)=H_{I}+c(e)$.

  4. 4.

For all $e\in E$ let $w_{I,P}(e)=H_{I}+c(e)\cdot(-1)^{d(P)}$.

  5. 5.

Let $k_{I}=\max_{S\in{\mathcal{I}}}|S|$ be the rank of $(E,{\mathcal{I}})$.

  6. 6.

Define $L_{I,P}=k_{I}\cdot H_{I}+T\cdot(-1)^{d(P)}$.

Now, for every EMB instance $I=(E,{\mathcal{I}},c,T)$, define the error
parameter of $I$ as

${\varepsilon}_{I}=\frac{1}{8\cdot(|E|+1)\cdot(T+1)\cdot\left(c(E)+1\right)}.$
(5)

Indeed, since the value selected for of the error parameter is sufficiently
small, we can use a $(1+{\varepsilon}_{I})$-approximation for $R_{P}(I)$ to
decide an EMB instance $I$.

######  Theorem 3.2.

Given an instance $I=(E,{\mathcal{I}},c,T)$ of EMB, and $P\in{\mathcal{Q}}$
with $P=(\textnormal{opt},{\mathcal{F}},\triangleleft)$, the following holds.

  1. 1.

If there is a solution $S$ for $R_{P}(I)$ such that $v_{I}(S)=k_{I}\cdot
H_{I}+T$, then $I$ is a “yes”-instance.

  2. 2.

If $I$ is a “yes”-instance then: $(i)$ $R_{P}(I)$ has a solution, and $(ii)$
every $(1+{\varepsilon}_{I})$-approximate solution $S$ for $R_{P}(I)$
satisfies $v_{I}(S)=k_{I}\cdot H_{I}+T$.

Using Theorem 3.2 and an assumed randomized Fully PTAS for the $P$-MOL
problem, we can decide EMB in time which contradicts Theorem 1.3. This gives
the proof of Theorem 1.1. We first prove Theorem 1.1, and later give the proof
of Theorem 3.2.

See 1.1

###### Proof.

Assume towards a contradiction that there is a randomized Fully PTAS
${\mathcal{A}}$ for oracle $P$-MOL. We use ${\mathcal{A}}$ to decide oracle-
EMB. Let $I=(E,{\mathcal{I}},c,T)$ be an oracle-EMB instance, and consider the
following randomized algorithm ${\mathcal{B}}$ that decides $I$.

  1. 1.

Construct the oracle $P$-MOL instance $R_{P}(I)$ with the membership oracle of
$(E,{\mathcal{I}})$.

  2. 2.

Execute ${\mathcal{A}}$ with the input $R_{P}(I)$ and ${\varepsilon}_{I}$.

  3. 3.

If ${\mathcal{A}}$ returns that $R_{P}(I)$ does not have a solution $-$ Return
”no” on $I$.

  4. 4.

Otherwise, let $S\leftarrow{\mathcal{A}}(R_{P}(I),{\varepsilon}_{I})$ be the
solution returned by ${\mathcal{A}}$.

  5. 5.

Return ”yes” on $I$ if and only if $v_{I}(S)=H_{I}\cdot k_{I}+T$.

Let $n=|E|+1$ and $m=c(E)+1$. Note that $R_{P}(I)$ can be naively constructed
from $I$ in time $\left(n\cdot(T+2)\cdot m\right)^{O(1)}$ using Definition
3.1. As ${\mathcal{A}}$ is a randomized Fully PTAS for oracle $P$-MOL, and by
the selection of the error parameter (5), the running time of ${\mathcal{B}}$
on $I$ is $\left(n\cdot(T+2)\cdot m\right)^{O(1)}$. We now show correctness.

  * •

If ${\mathcal{B}}$ returns “yes” on $I$, then Step 4 of the algorithm computes
a solution $S$ for $R_{p}(I)$ satisfying $v_{I}(S)=H_{I}\cdot k_{I}+T$. Thus,
by Theorem 3.2, $I$ is a “yes” instance.

  * •

If $I$ is a “yes” instance then $R_{P}(I)$ has a solution by Theorem 3.2. As
${\mathcal{A}}$ is a randomized Fully PTAS, with probability at least
$\frac{1}{2}$ ${\mathcal{A}}$ returns a $(1+{\varepsilon}_{I})$-approximate
solution $S$ for $R_{P}(I)$ in Step 4. By Theorem 3.2, $v_{I}(S)=H_{I}\cdot
k_{I}+T$ (with probability at least $\frac{1}{2}$). Thus, ${\mathcal{B}}$
returns “yes” on $I$ with probability at least $\frac{1}{2}$.

Hence, ${\mathcal{B}}$ is a randomized algorithm which decides the oracle-EMB
instance $I$ in time
$\left(n\cdot(T+2)\cdot m\right)^{O(1)}$. This is a contradiction to Theorem
1.3. ∎

In the remainder of this section we prove Theorem 3.2. We start with some
basic properties of the reduction outlined in Definition 3.1.

######  Lemma 3.3.

Given an instance $I=(E,{\mathcal{I}},c,T)$ of EMB, let $P\in{\mathcal{Q}}$
and consider a solution $S$ for $R_{P}(I)$ satisfying $v_{I}(S)=k_{I}\cdot
H_{I}+T$. Then, $S$ is a solution for $I$.

###### Proof.

Let ${\mathcal{M}}=(E,{\mathcal{I}})$. As $S$ is a solution for $R_{P}(I)$, it
holds that $S\in\textnormal{IS}({\mathcal{M}})$; thus, $|S|\leq k_{I}$. Assume
towards contradiction that $|S|<k_{I}$. Then,

$v_{I}(S)=|S|\cdot H_{I}+c(S)\leq(k_{I}-1)\cdot H_{I}+c(S)\leq(k_{I}-1)\cdot
H_{I}+c(E)<k_{I}\cdot H_{I}\leq k_{I}\cdot H_{I}+T.$

We reach a contradiction since $v_{I}(S)=k_{I}\cdot H_{I}+T$; thus,
$|S|=k_{I}$, and

$k_{I}\cdot H_{I}+T=v_{I}(S)=|S|\cdot H_{I}+c(S)=k_{I}\cdot H_{I}+c(S).$ (6)

As $|S|=k_{I}$, we have that $S$ is a basis of ${\mathcal{M}}$, and by (6),
$c(S)=T$. Hence, $S$ is a solution for $I$. ∎

The next result is the converse of the statement in Lemma 3.3.

######  Lemma 3.4.

Let $S$ be a solution for a given EMB instance $I=(E,{\mathcal{I}},c,T)$, and
let $P\in{\mathcal{Q}}$ where
$P=(\textnormal{opt},{\mathcal{F}},\triangleleft)$. Then, $S$ is a solution
for $R_{P}(I)$ of value $v_{I}(S)=k_{I}\cdot H_{I}+T$.

###### Proof.

Let ${\mathcal{M}}=(E,{\mathcal{I}})$. Since $S$ is a solution for $I$ we have
$S\in\textnormal{bases}({\mathcal{M}})$; thus,
$S\in{\mathcal{F}}({\mathcal{M}})$. Then,

$w_{I,P}(S)=|S|\cdot H_{I}+c(S)\cdot(-1)^{d(P)}=k_{I}\cdot
H_{I}+T\cdot(-1)^{d(P)}=L_{I,P}.$

The second equality holds since $S$ is a solution for $I$; thus, $|S|=k_{I}$
(as $S$ is a basis of ${\mathcal{M}}$), and $c(S)=T$. We conclude that $S$ is
a solution for $R_{P}(I)$. Finally, note that $S$ satisfies

$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}v_{I}(S)=|S|\cdot
H_{I}+c(S)=k_{I}\cdot
H_{I}+T~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\qed$

The next claim gives an upper bound on the optimal value for maximization MOL
problems. We then derive an analogous lower bound for minimization (non-
trivial) MOL problems.

######  Lemma 3.5.

Let $I=(E,{\mathcal{I}},c,T)$ be an EMB instance and $P\in{\mathcal{Q}}$,
where $P=(\textnormal{opt},{\mathcal{F}},\triangleleft)$ and
$\left(\textnormal{opt}\textnormal{ is }\max\right)$. Then, for every solution
$S$ of $R_{P}(I)$ it holds that $v_{I}(S)\leq k_{I}\cdot H_{I}+T$.

###### Proof.

Let $S$ be an optimal solution for $R_{P}(I)$. Thus, $|S|\leq k_{I}$ as
$S\in{\mathcal{I}}$. If $|S|<k_{I}$ then

$v_{I}(S)\leq(k_{I}-1)\cdot H_{I}+c(S)\leq(k_{I}-1)\cdot H_{I}+c(E)<k_{I}\cdot
H_{I}\leq k_{I}\cdot H_{I}+T.$

Otherwise, $|S|=k_{I}$. Consider the two cases for $\triangleleft$.

  1. 1.

$(\triangleleft\textnormal{ is}\leq)$. Then, $d(P)=0$ (see Definition 3.1);
thus, since $S$ is a solution for $R_{P}(I)$:

$v_{I}(S)=w_{I,P}(S)\leq L_{I,P}=k_{I}\cdot H_{I}+T.$

  2. 2.

$(\triangleleft\textnormal{ is}\geq)$. Then, $d(P)=1$. As $S$ is a solution
for $R_{P}(I)$,

$k_{I}\cdot H_{I}-c(S)=|S|\cdot H_{I}-c(S)=w_{I,P}(S)\geq L_{I,P}=k_{I}\cdot
H_{I}-T.$ (7)

By (7), it follows that $c(S)\leq T$; thus, $v_{I}(S)=k_{I}\cdot
H_{I}+c(S)\leq k_{I}\cdot H_{I}+T$.

In all the above cases, we have that $v_{I}(S)\leq k_{I}\cdot H_{I}+T$,
implying the statement of the lemma. ∎

Now, for minimization problems we have the next result.

######  Lemma 3.6.

Let $I=(E,{\mathcal{I}},c,T)$ be an EMB instance, and $P\in{\mathcal{Q}}$,
where $P=(\textnormal{opt},{\mathcal{F}},\triangleleft)$ and
$\left(\textnormal{opt}\textnormal{ is }\min\right)$. Then, for every solution
$S$ of $R_{P}(I)$, it holds that $v_{I}(S)\geq k_{I}\cdot H_{I}+T$.

###### Proof.

Let $S$ be a solution for $R_{P}(I)$. We consider two cases.

  1. 1.

$(\triangleleft\textnormal{ is}\geq)$. Then, $d(P)=0$; since $S$ is a solution
for $R_{P}(I)$,

$v_{I}(S)=w_{I,P}(S)\geq L_{I,P}=k_{I}\cdot H_{I}+T.$

  2. 2.

$(\triangleleft\textnormal{ is}\leq)$. Then, $d(P)=1$; since $P$ is a non-
trivial MOL problem (i.e., $P\in{\mathcal{Q}}$), it follows that
$\left({\mathcal{F}}\textnormal{ is }\textnormal{bases}\right)$. Thus, $S$ is
a solution for $R_{P}(I)$ such that $|S|=k_{I}$, and

$k_{I}\cdot H_{I}-c(S)=|S|\cdot H_{I}-c(S)=w_{I,P}(S)\leq L_{I,P}=k_{I}\cdot
H_{I}-T.$ (8)

By (8) it follows that $c(S)\geq T$; thus, $v_{I}(S)=k_{I}\cdot H_{I}+c(S)\geq
k_{I}\cdot H_{I}+T$.

In all of the above cases, we have that $v_{I}(S)\geq k_{I}\cdot H_{I}+T$,
implying the statement of the lemma. ∎

Using Lemmas 3.4, 3.3, 3.5 and 3.6, we can now prove Theorem 3.2. See 3.2

###### Proof.

We note that Property 1 follows directly from Lemma 3.3. For Property 2,
assume that $I$ is a “yes”-instance, then by Lemma 3.4, there is a solution
$D$ for $R_{P}(I)$ such that $v_{I}(D)=H_{I}\cdot k_{I}+T$. It remains to show
Property 2. $(ii)$. Let $S$ be a $(1+{\varepsilon}_{I})$-approximate solution
for $R_{P}(I)$. We distinguish between two cases.

  1. 1.

$(\textnormal{opt}\textnormal{ is}\max)$. Then, by Lemma 3.5,

$0\leq H_{I}\cdot k_{I}+T-v_{I}(S).$

Moreover, since $S$ is a $(1+{\varepsilon}_{I})$-approximate solution for
$R_{P}(I)$, and $D$ is a solution for $R_{P}(I)$,

$H_{I}\cdot k_{I}+T-v_{I}(S)\leq H_{I}\cdot
k_{I}+T-\frac{v_{I}(D)}{(1+{\varepsilon}_{I})}=\frac{{\varepsilon}_{I}\cdot\left(H_{I}\cdot
k_{I}+T\right)}{(1+{\varepsilon}_{I})}\leq{\varepsilon}_{I}\cdot\left(H_{I}\cdot
k_{I}+T\right).$

By the above, it follows that

$\left|v_{I}(S)-\left(H_{I}\cdot
k_{I}+T\right)\right|\leq{\varepsilon}_{I}\cdot\left(H_{I}\cdot
k_{I}+T\right).$

  2. 2.

$(\textnormal{opt}\textnormal{ is}\min)$. This case is analogous to the above.
By Lemma 3.6,

$0\leq v_{I}(S)-\left(H_{I}\cdot k_{I}+T\right).$

Since $S$ is a $(1+{\varepsilon}_{I})$-approximate solution for $R_{P}(I)$,
and $D$ is a solution for $R_{P}(I)$,

$v_{I}(S)-\left(H_{I}\cdot k_{I}+T\right)\leq(1+{\varepsilon}_{I})\cdot
v_{I}(D)-\left(H_{I}\cdot
k_{I}+T\right)={\varepsilon}_{I}\cdot\left(H_{I}\cdot k_{I}+T\right).$

By the above,

$\left|v_{I}(S)-\left(H_{I}\cdot
k_{I}+T\right)\right|\leq{\varepsilon}_{I}\cdot\left(H_{I}\cdot
k_{I}+T\right).$

Thus in both cases it holds that,

$\left|v_{I}(S)-\left(H_{I}\cdot
k_{I}+T\right)\right|\leq{\varepsilon}_{I}\cdot\left(H_{I}\cdot
k_{I}+T\right).$ (9)

Let $n=|E|+1$ and $m=c(E)+1$. Then, by the selection of ${\varepsilon}_{I}$ in
(5),

${\varepsilon}_{I}\cdot\left(H_{I}\cdot k_{I}+T\right)=\frac{H_{I}\cdot
k_{I}+T}{8\cdot n\cdot(T+1)\cdot m}\leq\frac{2\cdot m\cdot n+T}{8\cdot
n\cdot(T+1)\cdot m}<\frac{4\cdot m\cdot n\cdot(T+1)}{8\cdot n\cdot(T+1)\cdot
m}=\frac{1}{2}.$ (10)

The first inequality holds since $k_{I}\leq|E|$ and $H_{I}\leq 2\cdot m$.
Therefore, by (9) and (10),

$\left|v_{I}(S)-\left(H_{I}\cdot
k_{I}+T\right)\right|\leq{\varepsilon}_{I}\cdot\left(H_{I}\cdot
k_{I}+T\right)<\frac{1}{2}.$ (11)

Since $v_{I}(S)\in\mathbb{N}$ by Definition 3.1, it follows from (11) that
$v_{I}(S)=H_{I}\cdot k_{I}+T$. This gives the statement of the theorem. ∎

##  4 Lower Bounds in the Standard Computational Model

Our hardness result in Section 2 shows that oracle Exact Matroid Basis (EMB)
is hard, leading to the unconditional lower bounds for all non-trivial oracle
MOL problems in Section 3. Nonetheless, these hardness results consider
matroids with general membership oracles, and do not give a lower bound for
matroids that can be efficiently encoded. This is particularly important, as
in some settings oracle models differ from non-oracle models w.r.t complexity
[6, 9]. Moreover, some matroids show up in problems that can be encoded
efficiently. This includes partition matroids, graphic matroids, linear
matroids, etc (see, e.g., [36] for a survey on various families of matroids).
Next, we formally define an efficient encoding of matroids.

######  Definition 4.1.

A function $f:\\{0,1\\}^{*}\rightarrow 2^{\mathbb{N}}\times
2^{2^{\mathbb{N}}}$ is called matroid decoder if for every $I\in\\{0,1\\}^{*}$
it holds that $f(I)=\left(E_{f(I)},{\mathcal{I}}_{f(I)}\right)$ is a matroid,
and the following holds.

  1. 1.

There is an algorithm that given $I\in\\{0,1\\}^{*}$ returns $E_{f(I)}$ in
time $|I|^{O(1)}$.

  2. 2.

There is an algorithm that given $I\in\\{0,1\\}^{*}$ and $S\subseteq E_{f(I)}$
decides if $S\in{\mathcal{I}}_{f(I)}$ in time $|I|^{O(1)}$.

There is a simple matroid decoder that can decode every matroid
$(E,{\mathcal{I}})$ (such that $E\subseteq\mathbb{N}$), in which the encoding
$I$ explicitly lists ${\mathcal{I}}$. However, using such a matroid decoder,
the encoding size of a matroid might be very large, up to
$|I|=\Omega\left(2^{|E|}\right)$, while we often seek algorithms with running
times polynomial in $|E|$. One way to overcome this difficulty is via the
oracle model considered in previous sections. However, our results in this
model may suggest that the hardness of EMB and MOL problems is due to the
intrinsic hardness of the oracle model. Yet, there are families of matroids
with very efficient encoding. For example, a uniform matroid
$(E,{\mathcal{I}})$, where ${\mathcal{I}}=\\{S\subseteq E~{}|~{}|S|\leq k\\}$,
can be efficiently encoded using $I=(E,k)\in\\{0,1\\}^{*}$. Clearly, the time
to decide membership of a given subset $S\subseteq E$ depends only on $|S|$
and $k$. Another example is given in Figure 3.

We start with a definition of an encoded variant of EMB. We technically define
a different problem for every decoder $f$. The definition of the problem is
analogous to the versions of EMB considered earlier in the paper, besides that
the matroid is given via an arbitrary bit-string $I\in\\{0,1\\}^{*}$, that a
matroid decoder $f$ decodes into a matroid $f(I)$.

$f$-decoded Exact Matroid Basis ($f$-decoded EMB)
---
Decoder |  $f:\\{0,1\\}^{*}\rightarrow 2^{\mathbb{N}}\times 2^{2^{\mathbb{N}}}$ is a matroid decoder.
Instance |  $(I,c,T)$, where $I\in\\{0,1\\}^{*}$, $c:E_{f(I)}\rightarrow\mathbb{N}$, $T\in\mathbb{N}$.
Solution |  A basis $S$ of the matroid $f(I)$ such that $c(S)=T$.
Objective |  Decide if there is a solution.

As a simple example, consider the $f_{\textsf{u}}$-decoded EMB problem, for a
specific matroid decoder $f_{\textsf{u}}$ that decodes uniform matroids. The
matroid decoder $f_{\textsf{u}}$ interprets every $I\in\\{0,1\\}^{*}$ as
$I=(E,k)$ where $E$ is a set (of numbers) and $k\in\mathbb{N}$, and returns
the uniform matroid $f_{\textsf{u}}(I)=(E,{\mathcal{I}})$ such that
${\mathcal{I}}=\\{S\subseteq E~{}|~{}|S|\leq k\\}$; clearly, $f_{\textsf{u}}$
is a matroid decoder. Thus, an instance of $f_{\textsf{u}}$-decoded EMB is a
tuple $U=((E,k),c,T)$ and a solution of $U$ is $S\subseteq E$ such that
$|S|=k$ and $c(S)=T$; the goal, as before, is to decide if there is a
solution. This problem is commonly known as the $k$-subset sum.

$\bf{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}U}$$\bf{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}V}$$\bf{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}W}$$u_{1}$$u_{2}$$u_{3}$$v_{1}$$v_{2}$$w_{3}$$w_{2}$$w_{1}$
Figure 3:  An example of a partition matroid $(E,{\mathcal{I}})$, which can be
efficiently encoded. The ground set is
$E=\\{u_{1},u_{2},u_{3},v_{1},v_{2},w_{1},w_{2},w_{3}\\}$, partitioned into
three sets: $U,V,W$. The independent sets are all subsets of $E$ containing at
most one element from $U,V$, and $W$; that is, ${\mathcal{I}}=\\{S\subseteq
E~{}|~{}\forall X\in\\{U,V,W\\}:|S\cap X|\leq 1\\}$. A simple efficient
encoding of $(E,{\mathcal{I}})$ is $I=(E,U,V,W)$. Membership can be decided
efficiently given $I$, by checking the feasibility of a given set $S$ w.r.t.
$U,V$ and $W$.

Recall that Theorem 1.3 asserts that oracle-EMB does not admit a pseudo-
polynomial time algorithm. However, this does not rule out that
hypothetically, for every matroid decoder $f$ there is a pseudo-polynomial
time algorithm for $f$-decoded EMB. The next result excludes this option.

######  Theorem 4.2.

Assuming $\textnormal{P}\neq\textnormal{NP}$, there is a matroid decoder $f$
such that there is no algorithm for $f$-decoded EMB that for any $f$-decoded
EMB instance $U=(I,c,T)$, where $n=\left|E_{f(I)}\right|+1$ and
$m=c\left(E_{f(I)}\right)+1$, runs in time $(n\cdot(T+2)\cdot m)^{O(1)}$.

The proof of Theorem 4.2 is given towards the end of this section. Analogously
to our hardness result for oracle MOL problems, we use Theorem 4.2 to give a
hardness result for an encoded version of MOL problems. For every matroid
decoder $f$ and every $P\in{\mathcal{P}}$, we define a variant of the
$P$-matroid optimization with a linear constraint ($P$-MOL) problem in which
the matroid is given via an arbitrary bit-string which a matroid decoder $f$
decodes into a matroid. Formally, let $P\in{\mathcal{P}}$, where
$P=(\textnormal{opt},{\mathcal{F}},\triangleleft)$, be the parameters of the
$P$-MOL problem. For a matroid decoder $f$, we define the $f$-decoded $P$-MOL
problem as follows.

$f$-decoded $P$-matroid optimization with a linear constraint (f-decoded
$P$-MOL)
---
Decoder |  $f:\\{0,1\\}^{*}\rightarrow 2^{\mathbb{N}}\times 2^{2^{\mathbb{N}}}$ is a matroid decoder.
Instance |  $(I,v,w,L)$, where $I\in\\{0,1\\}^{*}$, $v:E_{f(I)}\rightarrow\mathbb{R}_{\geq 0}$, $w:E_{f(I)}\rightarrow\mathbb{R}_{\geq 0}$, $L\in\mathbb{R}_{\geq 0}$.
Objective |  $\textnormal{opt}~{}v(S)\text{ s.t. }S\in{\mathcal{F}}\left(f(I)\right),~{}w(S)\triangleleft L$.

For example, consider the encoded version of the $P$-MOL for
$P=(\max,\textnormal{IS},\leq)$ with the matroid decoder $f_{\textsf{u}}$ that
decodes uniform matroids. An instance of the $f_{\textsf{u}}$-decoded $P$-MOL
problem is a tuple $U=(I,v,w,L)$ where $I=(E,k)$ is a bit-string used for
extracting the uniform matroid $f_{\textsf{u}}(I)=(E,{\mathcal{I}})$ such that
${\mathcal{I}}=\\{S\subseteq E~{}|~{}|S|\leq k\\}$, $v$ is the value function,
$w$ is the weight function, and $L$ is the bound. A solution of $U$ is
$S\subseteq E$ such that $|S|\leq k$ and $w(S)\leq L$; the goal is to find a
solution $S$ of maximum value $v(S)$. This problem is widely known as knapsack
with cardinality constraint.

Recall that
${\mathcal{Q}}={\mathcal{P}}\setminus\\{(\min,\textnormal{IS},\leq)\\}$ is the
set of parameters for non-trivial MOL problems. Using the hardness of
$f$-decoded, for some matroid decoder $f$ (details on $f$ are given towards
the end of the section), we show the hardness of the $f$-decoded variant of
all non-trivial MOL problems.

######  Theorem 4.3.

Assuming $\textnormal{P}\neq\textnormal{NP}$, for any $P\in{\mathcal{Q}}$
there is a matroid decoder $f$ such that there is no Fully PTAS for
$f$-decoded $P$-MOL.

In the remainder of this section, we prove Theorem 4.2 and Theorem 4.3. The
matroid decoder used in our proofs decodes a subclass of the $\Pi$-matroid
family (see Section 2), in which the secret family $\Pi$ consists of the
solutions for a boolean satisfiability problem (SAT) instance.

In a SAT instance $A=(V,\bar{V},{\mathcal{C}})$ with $n\in\mathbb{N}$
variables (in a slightly simplified notation), we are given a set
$V=\\{v_{1},\ldots,v_{n}\\}$ of variables, their negations
$\bar{V}=\\{\bar{v}_{1},\ldots,\bar{v}_{n}\\}$, and a set
${\mathcal{C}}\subseteq 2^{V\cup\bar{V}}$ of clauses. The goal is to decide if
there is a set $S\subseteq[n]$ satisfying that for all $C\in{\mathcal{C}}$
there is $i\in[n]$ such that one of the following holds.

  * •

$v_{i}\in C$ and $i\in S$.

  * •

$\bar{v}_{i}\in C$ and $i\notin S$.

Such a set $S$ is called a solution of $A$; let $\mathcal{S}(A)$ be the set of
solutions of a SAT instance $A$. In addition, let $n(A)=n$ be the number of
variables in the instance $A$. The family of SAT-matroids is the subfamily of
$\Pi$-matroids where $\Pi=\mathcal{S}(A)$ for some SAT instance $A$ (for the
notation and definition of $\Pi$-matroids, see Definition 2.1). Specifically,

######  Definition 4.4.

Let $A$ be a SAT instance, $k\in\left[n(A)\right]$, and
$\alpha\in\left[{n(A)}^{2}\right]$. Define the SAT-matroid on $A,k,\alpha$ as
$M_{n(A),k,\alpha}(\mathcal{S}(A))=\left(\left[n(A)\right],{\mathcal{I}}_{n(A),k,\alpha}(\mathcal{S}(A))\right)$.

We show below that SAT-matroids can be encoded efficiently. For every
$I\in\\{0,1\\}^{*}$, we interpret $I$ as $I=(A,k,\alpha)$, where $A$ is a SAT
instance, $k\in\left[n(A)\right]$, and $\alpha\in\left[{n(A)}^{2}\right]$;
w.l.o.g., we may assume that every $I=(A,k,\alpha)\in\\{0,1\\}^{*}$ can be
interpreted in that manner; moreover, we can assume that $n(A)\leq|A|$, where
$|A|$ is the encoding size of $A$. The following definition defines a matroid
decoder that decodes SAT-matroids from a bit-string.

######  Definition 4.5.

Define the SAT-decoder as the function
$f_{\textnormal{SAT}}:\\{0,1\\}^{*}\rightarrow 2^{\mathbb{N}}\times
2^{2^{\mathbb{N}}}$ such that for all $I=(A,k,\alpha)\in\\{0,1\\}^{*}$ it
holds that $f_{\textnormal{SAT}}(I)=M_{n(A),k,\alpha}(\mathcal{S}(A))$.

In the next result, we show that the SAT-decoder $f_{\textnormal{SAT}}$ is
indeed a matroid decoder.

######  Lemma 4.6.

$f_{\textnormal{SAT}}$ is a matroid decoder such that $|I|=|A|^{O(1)}$ for
every $I=(A,k,\alpha)\in\\{0,1\\}^{*}$.

Recall the sets $\mathcal{J}_{n,k}$, $\mathcal{K}_{n,k,\alpha}$,
$\mathcal{L}_{n,k,\alpha}(\Pi)$ and ${\mathcal{I}}_{n,k,\alpha}(\Pi)$ were
defined in Definition 2.1.

###### Proof.

We first show that $f_{\textnormal{SAT}}$ is a matroid decoder. For all
$I=(A,k,\alpha)\in\\{0,1\\}^{*}$ it holds that $\mathcal{S}(A)\subseteq
2^{\left[n(A)\right]}$; thus, by Lemma 2.2 it holds that
$f_{\textnormal{SAT}}(I)$ returns a matroid. Moreover, for all
$I=(A,k,\alpha)\in\\{0,1\\}^{*}$ it holds that $k,\alpha={n(A)}^{O(1)}$ and
$n(A)\leq|A|$ by our encoding; hence, $|I|=|A|^{O(1)}$. It remains to prove
that $f_{\textnormal{SAT}}$ satisfies Items 1 and 2 in Definition 4.1.

  1. 1.

Item 1. Given $I=(A,k,\alpha)\in\\{0,1\\}^{*}$, we can compute
$E_{f_{\textnormal{SAT}}(I)}=\left[n(A)\right]$ in time $|I|^{O(1)}$ by
identifying the number of variables (i.e., $n(A)$) in $A$.

  2. 2.

Item 2. Let $I=(A,k,\alpha)\in\\{0,1\\}^{*}$ and let $n=n(A)$; we show that we
can decide membership in the matroid $f_{\textnormal{SAT}}(I)$ in time
$|I|^{O(1)}$. For every $S\subseteq\left[n\right]$ we can compute $|S|$ and
$\textsf{sum}(S)$ in time $|I|^{O(1)}$. Thus, validating if
$S\in\mathcal{J}_{n,k}$ or $S\in\mathcal{K}_{n,k,\alpha}$ can be computed in
time $|I|^{O(1)}$ regardless of $\mathcal{S}(A)$. In addition, deciding if
$S\in\mathcal{S}(A)$ can be computed in time $|A|^{O(1)}=|I|^{O(1)}$ by
confirming that all clauses are satisfied. Thus, by (2) we can decide if
$S\in\mathcal{L}_{n,k,\alpha}(\mathcal{S}(A))$. Overall, deciding whether
$S\in\mathcal{J}_{n,k}$, $S\in\mathcal{K}_{n,k,\alpha}$, or
$S\in\mathcal{L}_{n,k,\alpha}(\mathcal{S}(A))$ can be computed in time
$|I|^{O(1)}$. By the above and (2), we can compute in time $|I|^{O(1)}$
correctly if a set $S$ belongs to
${\mathcal{I}}_{f_{\textnormal{SAT}}(I)}={\mathcal{I}}_{n,k,\alpha}(\mathcal{S}(A))$.

Thus, $f_{\textnormal{SAT}}$ is a matroid decoder by Definition 4.1, which
gives the statement of the lemma. ∎

We will use an algorithm for $f$-decoded EMB to obtain an algorithm for SAT.
To this end, consider the following family of structured
$f_{\textnormal{SAT}}$-decoded EMB instances.

######  Definition 4.7.

An $f_{\textnormal{SAT}}$-decoded EMB instance $(I,c,T)$, where
$I=(A,k,\alpha)$ is called structured if $\alpha\in\left[{n(A)}^{2}\right]$,
$T=\alpha$, and $c:\left[n(A)\right]\rightarrow\mathbb{N}$ such that for all
$i\in\left[n(A)\right]$ it holds that $c(i)=i$

The next observation immediately follows from the definition of structured
$f_{\textnormal{SAT}}$-decoded EMB instances and SAT-matroids.

######  Observation 4.8.

for any structured $f_{\textnormal{SAT}}$-decoded EMB instance $U=(I,c,T)$,
where $I=(A,k,\alpha)$, and $S\subseteq\left[n(A)\right]$, it holds that: $S$
is a solution for $U$ if and only if $S\in\mathcal{S}(A)$, $|S|=k$, and
$\textnormal{{sum}}(S)=c(S)=\alpha$.

We show that given a polynomial algorithm that decides structured
$f_{\textnormal{SAT}}$-decoded EMB instances, we can decide SAT. This result
easily imply Theorem 4.2 as shown afterwards.

######  Lemma 4.9.

Assuming $\textnormal{P}\neq\textnormal{NP}$, there no algorithm that decides
every $f_{\textnormal{SAT}}$-decoded EMB structured instance $(I,c,T)$ in time
$|I|^{O(1)}$.

###### Proof.

Assume that $\textnormal{P}\neq\textnormal{NP}$ and assume towards a
contradiction that there is an algorithm ${\mathcal{A}}$ that decides every
$f_{\textnormal{SAT}}$-decoded EMB structured instance $(I,c,T)$ in time
$|I|^{O(1)}$. We describe the following algorithm ${\mathcal{B}}$ which
decides SAT using ${\mathcal{A}}$. Let $A$ be a SAT instance and let $n=n(A)$.

  1. 1.

For every $k\in\left[n\right]$ and $\alpha\in\left[n^{2}\right]$, let
$I_{k,\alpha}=(A,k,\alpha)$; execute ${\mathcal{A}}$ on the structured
instance $U_{k,\alpha}=(I_{k,\alpha},c,\alpha)$.

  2. 2.

If $\emptyset$ is a solution for $A$, return “yes” on $A$.

  3. 3.

If there are $k\in\left[n\right]$ and $\alpha\in\left[n^{2}\right]$ such that
${\mathcal{A}}$ returns “yes” on $U_{k,\alpha}$, return “yes” on $A$.

  4. 4.

Otherwise, return “no” on $A$.

To show that ${\mathcal{B}}$ decides SAT, consider the following cases.

  * •

$A$ is a “yes”-instance. Then, there is a solution $S\in\mathcal{S}(A)$. If
$\emptyset\in\mathcal{S}(A)$ then ${\mathcal{B}}$ returns “yes” on $A$.
Otherwise, there are $k\in[n]$, $\alpha\in\left[n^{2}\right]$, and a solution
$S\in\mathcal{S}(A)$ such that $|S|=k$ and $\textnormal{{sum}}(S)=\alpha$.
Since $U_{k,\alpha}$ is structured, we have $c(S)=\alpha$; therefore, $S$ is a
solution for $U_{k,\alpha}$ by 4.8. Consequently, ${\mathcal{A}}$ returns
“yes” on $U_{k,\alpha}$; hence, ${\mathcal{B}}$ returns “yes” on $A$.

  * •

$A$ is a “no”-instance. Then, $\mathcal{S}(A)=\emptyset$. Assume towards a
contradiction that ${\mathcal{B}}$ returns “yes” on $A$. Thus, since
$\emptyset\notin\mathcal{S}(A)$, there are $k\in[n]$ and
$\alpha\in\left[n^{2}\right]$ such that ${\mathcal{A}}$ returns “yes” on
$U_{k,\alpha}$, implying that there is a solution $S$ for $U_{k,\alpha}$.
Since $U_{k,\alpha}$ is structured, by 4.8 it holds that $S\in\mathcal{S}(A)$.
This is a contradiction that $\mathcal{S}(A)=\emptyset$. Thus, ${\mathcal{B}}$
returns “no” on $A$.

Hence, ${\mathcal{B}}$ decides the SAT instance $A$ correctly. We analyze the
running time below.

By our encoding, it holds that $n\leq|A|$ as $A$ contains $n$ distinct
variables. In addition, observe that the identity function
$c:[n]\rightarrow[n]$ can be encoded using at most $n\cdot\log(n)$ bits (this
is the weight function of every structured instance $U_{k,\alpha}$ constructed
in the algorithm, for $k\in[n]$ and $\alpha\in\left[n^{2}\right]$). Then, for
all $k\in[n]$ and $\alpha\in\left[n^{2}\right]$ observe that the encoding of
the instance $U_{k,\alpha}$ satisfies:

$|U_{k,\alpha}|=|A|+k+\alpha+n\cdot\log(n)\leq|A|+n+n^{2}+n\cdot\log(n)=O\left(|A|^{2}\right).$

Moreover, the number of iterations (i.e., the number of distinct options for
the parameters $k,\alpha$) is bounded by $n\cdot n^{2}=n^{3}=O(|A|^{3})$.
Thus, the running time of each iteration is bounded by
$|U_{k,\alpha}|^{O(1)}=|A|^{O(1)}$ by the running time guarantee of
${\mathcal{A}}$. Therefore, our algorithm decides SAT in time $|A|^{O(1)}$.
Since SAT is known to be NP-Hard (see, e.g., [22] for more details), we reach
a contradiction to the existence of ${\mathcal{A}}$. ∎

From the above result, the hardness of the more general
$f_{\textnormal{SAT}}$-decoded EMB easily follows. As an immediate corollary,
Theorem 4.10 gives the proof of Theorem 4.2.

######  Theorem 4.10.

Assuming $\textnormal{P}\neq\textnormal{NP}$, there is no algorithm for
$f_{\textnormal{SAT}}$-decoded EMB that runs in time $(n\cdot(T+2)\cdot
m)^{O(1)}$, for any $f_{\textnormal{SAT}}$-decoded EMB instance $U=(I,c,T)$
where $n=\left|E_{f_{\textnormal{SAT}}(I)}\right|+1$ and
$m=c\left(E_{f_{\textnormal{SAT}}(I)}\right)+1$.

###### Proof.

Let $U=(I,c,T)$ be a structured $f_{\textnormal{SAT}}$-decoded EMB instance
and let $I=(A,k,\alpha)$. Recall that by our encoding it holds that
$|I|\geq|A|\geq n(A)$. Thus, since $U$ is structured, it follows that
$\left|E_{f_{\textnormal{SAT}}(I)}\right|=n(A)\leq|I|$ and

$c\left(E_{f_{\textnormal{SAT}}(I)}\right)=\textsf{sum}\left(\left[n(A)\right]\right)\leq\frac{n(A)\cdot(n(A)+1)}{2}=O\left(|I|^{2}\right).$

Thus, by the above, an algorithm ${\mathcal{A}}$ that decides every
$f_{\textnormal{SAT}}$-EMB instance $(I^{\prime},c^{\prime},T^{\prime})$ in
time $(n^{\prime}\cdot(T^{\prime}+2)\cdot m^{\prime})^{O(1)}$, where
$n^{\prime}=|E_{f_{\textnormal{SAT}}(I^{\prime})}|+1$ and
$m^{\prime}=c\left(E_{f_{\textnormal{SAT}}(I)}\right)+1$, in particular
decides $U$ in time $|I|^{O(1)}$. As $U$ is an arbitrary structured instance,
unless $\textnormal{P}=\textnormal{NP}$, by Lemma 4.9 such an algorithm
${\mathcal{A}}$ cannot exist. ∎

Finally, we show that the variants of non-trivial matroid optimization with a
linear constraint (MOL) problems, in which the decoding is performed by the
SAT-decoder $f_{\textnormal{SAT}}$, do not admit Fully PTAS under the standard
assumption $\textnormal{P}\neq\textnormal{NP}$. The proof is similar to the
proof of Theorem 1.1 in Section 3. Lemma 4.11 directly gives the proof of
Theorem 4.3.

######  Lemma 4.11.

Assuming $\textnormal{P}\neq\textnormal{NP}$, for any $P\in{\mathcal{Q}}$
there is no Fully PTAS for $f_{\textnormal{SAT}}$-decoded $P$-MOL.

###### Proof.

Assume that $\textnormal{P}\neq\textnormal{NP}$ and assume towards a
contradiction that there is a Fully PTAS ${\mathcal{A}}$ for
$f_{\textnormal{SAT}}$-decoded $P$-MOL. We use ${\mathcal{A}}$ to decide
$f_{\textnormal{SAT}}$-decoded EMB. Let $U=(I,c,T)$ be an
$f_{\textnormal{SAT}}$-decoded EMB instance. Consider the following algorithm
${\mathcal{B}}$ that decides $U$. In the algorithm, we use the reduction
described in Definition 3.1 and an error parameter defined in (5).

  1. 1.

Construct the $f_{\textnormal{SAT}}$-decoded $P$-MOL instance
$X=(I,v_{J},w_{J,P},L_{J,P})$, where
$J=\left(E_{f_{\textnormal{SAT}}(I)},{\mathcal{I}}_{f_{\textnormal{SAT}}(I)},c,T\right)$
is an EMB instance.

  2. 2.

Execute ${\mathcal{A}}$ with the input $X$ and ${\varepsilon}_{J}$ (see (5)).

  3. 3.

If ${\mathcal{A}}$ returns “no” on $X$: Return “no” on $U$.

  4. 4.

Otherwise, let $S\leftarrow{\mathcal{A}}(X,{\varepsilon}_{J})$ be the returned
solution by ${\mathcal{A}}$.

  5. 5.

Return “yes” on $U$ if and only if $v_{J}(S)=H_{J}\cdot k_{J}+T$.

Observe that $U,J$ share the same matroid, weight function, and target value;
the only difference between them is the representation of the matroid, that is
encoded in $U$ while in $J$ the representation of the matroid is not
specified. Similarly, $X$ and $R_{P}(J)$ also share the same matroid, value
function, weight function, and bound; the only difference between them is that
$X$ gives a concrete encoding of the matroid.

Let $n=|E|+1$ and let $m=c(E)+1$. Note that $X$ can be trivially constructed
from $U$ in time $\left(n\cdot(T+2)\cdot m\right)^{O(1)}$ by Definition 3.1.
Thus, the running time of ${\mathcal{B}}$ on $U$ is $\left(n\cdot(T+2)\cdot
m\right)^{O(1)}$, since ${\mathcal{A}}$ is a Fully PTAS for
$f_{\textnormal{SAT}}$-decoded $P$-MOL and by the selection of the error
parameter ${\varepsilon}_{J}$ in (5). We now show correctness.

  * •

If ${\mathcal{B}}$ returns “yes” on $U$. Then, Step 4 of the algorithm
computes a solution $S$ for $X$ satisfying $v_{J}(S)=H_{J}\cdot k_{J}+T$.
Clearly, $S$ is a solution for $R_{P}(J)$ as well. By Theorem 3.2, $S$ is also
a solution for $J$. As $J$ and $U$ share the same matroid, weight function,
and target value, we conclude that $S$ is a solution for $U$. Therefore, $U$
is a “yes”-instance.

  * •

If $U$ is a “yes”-instance. Then, $J$ has a solution. Therefore, by Theorem
3.2 it holds that $R_{P}(J)$ has a solution, which implies that $X$ has a
solution. Thus, since ${\mathcal{A}}$ is a Fully PTAS for
$f_{\textnormal{SAT}}$-decoded $P$-MOL, ${\mathcal{A}}$ returns a
$(1+{\varepsilon}_{J})$-approximate solution $S$ for $X$; clearly, $S$ is also
a $(1+{\varepsilon}_{J})$-approximate solution for $R_{P}(J)$. Then, by
Theorem 3.2 it follows that $v_{J}(S)=H_{J}\cdot k_{J}+T$. Thus,
${\mathcal{B}}$ returns “yes” on $U$.

Hence, ${\mathcal{B}}$ decides $f_{\textnormal{SAT}}$-decoded EMB in time
$\left(n\cdot(T+2)\cdot m\right)^{O(1)}$, contradicting Theorem 4.10. ∎

##  5 Discussion

In this paper, we derive lower bounds for the family of matroid optimization
problems with a linear constraint. We show that none of the (non-trivial)
members of this family admits a Fully PTAS. In particular, this rules out a
Fully PTAS for previously studied problems such as budgeted matroid
independent set, constrained minimum basis of a matroid, and knapsack cover
with a matroid. As BM and CMB admit an Efficient PTAS, our lower bounds
resolve the complexity status of these problems, which has been open also for
the generalization of budgeted matroid intersection [12, 2, 18]. Our
preliminary study shows that using the techniques of [25], we may be able to
derive Efficient PTAS for all MOL problems. This would imply that Theorem 1.1
gives a tight lower bound for the entire MOL family. We leave the details for
future work.

A key result of this paper is that exact matroid basis (EMB) does not admit a
pseudo-polynomial time algorithm, unlike the known special cases of $k$-subset
sum and EMB on a linear matroid. Our proofs can be used to obtain lower bounds
for other problems. For example, the hardness result for EMB can be adapted to
yield lower bounds for related parameterized problems [21, 17]. Moreover, the
proof of Theorem 1.1 can be modified to show that an Efficient PTAS for a non-
trivial MOL problem with running time
$f\left(\frac{1}{{\varepsilon}}\right)\cdot\textnormal{poly}(n)$ must satisfy
$f\left(\frac{1}{{\varepsilon}}\right)=\Omega\left(2^{{\varepsilon}^{-\frac{1}{4}}}\right)$.
We leave these generalizations of our results to a later version of this
paper.

Our results build on the $\Pi$-matroid family introduced in this paper. Such
matroids exploit the interaction between a weight function and the underlying
matroid constraint of the given problem. Aside from the implications of our
results for previously studied problems, the new subclass of $\Pi$-matroids
may enable to derive lower bounds for other problems. For example, consider
the generalization of BM where the objective function is submodular and
monotone. This is known as monotone submodular maximization with a knapsack
and a matroid constraint [11]. Indeed, if the knapsack constraint is removed,
there is a tight $\left(1-\frac{1}{e}\right)$-approximation for the problem
[4]. The same bound holds if we relax the matroid constraint [39]. However,
the best known approximation for the problem with a knapsack and a matroid
constraint is $\left(1-\frac{1}{e}-{\varepsilon}\right)$ [11]. This setting
resembles the status of MOL problems prior to our work, where removing either
the linear or the matroid constraint induces a substantially easier problem.
The potential use of $\Pi$-matroid variants to rule out a
$\left(1-\frac{1}{e}\right)$-approximation for the above problem remains an
interesting open question. One additional consequence of our lower bound in a
different domain is that solving configuration LPs for packing problems with a
matroid constraint (e.g., [23, 16]) cannot be solved for general matroids in
FPTAS time using the standard ellipsoid methods.

We show unconditional hardness results in the oracle model (even if
randomization is allowed), and give analogous lower bounds where the matroids
are encoded as part of the input, assuming
$\textnormal{P}\neq\textnormal{NP}$. Our construction in Section 4 can be used
to derive hardness results for other matroid problems in non-oracle models.
Specifically, we can obtain in the standard computational model hardness
results analogous to those in the oracle model of [27]. This includes a proof
that it is NP-hard to decide if a given matroid is uniform, analogous to the
unconditional hardness result in the oracle model of [27]. We leave these
results for future work.

Our lower bounds for MOL problems on general matroids call for a more
comprehensive study of these problems on restricted classes of matroids. We
note the existence of Fully PTASs for MOL problems on some restricted matroid
classes, e.g., BM on a laminar matroid or KCM on a partition matroid. The
question whether (non-trivial) MOL problems admit Fully PTAS on broader
matroid classes, such as graphical matroids or linear matroids, remains open.
In particular, it would be interesting to obtain a Fully PTAS for constrained
minimum spanning tree [25] and BM on a linear matroid $-$ or show that one
does not exist.

## References

  * [1] Andersen, K.A., Jörnsten, K., Lind, M.: On bicriterion minimal spanning trees: An approximation. Computers & Operations Research 23(12), 1171–1182 (1996)
  * [2] Berger, A., Bonifaci, V., Grandoni, F., Schäfer, G.: Budgeted matching and budgeted matroid intersection via the gasoline puzzle. Mathematical Programming 128(1), 355–372 (2011)
  * [3] Bringmann, K., Nakos, V.: A fine-grained perspective on approximating subset sum and partition. In: Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA). pp. 1797–1815. SIAM (2021)
  * [4] Calinescu, G., Chekuri, C., Pal, M., Vondrák, J.: Maximizing a monotone submodular function subject to a matroid constraint. SIAM Journal on Computing 40(6), 1740–1766 (2011)
  * [5] Camerini, P.M., Galbiati, G., Maffioli, F.: Random pseudo-polynomial algorithms for exact matroid problems. Journal of Algorithms 13(2), 258–273 (1992)
  * [6] Canetti, R., Goldreich, O., Halevi, S.: The random oracle methodology, revisited. Journal of the ACM (JACM) 51(4), 557–594 (2004)
  * [7] Caprara, A., Kellerer, H., Pferschy, U., Pisinger, D.: Approximation algorithms for knapsack problems with cardinality constraints. European Journal of Operational Research 123(2), 333–345 (2000)
  * [8] Chakaravarthy, V.T., Choudhury, A.R., Natarajan, S.R., Roy, S.: Knapsack cover subject to a matroid constraint. In: Proc. FSTTCS (2013)
  * [9] Chang, R., Chor, B., Goldreich, O., Hartmanis, J., Håstad, J., Ranjan, D., Rohatgi, P.: The random oracle hypothesis is false. Journal of Computer and System Sciences 49(1), 24–39 (1994)
  * [10] Chekuri, C., Khanna, S.: A polynomial time approximation scheme for the multiple knapsack problem. SIAM Journal on Computing 35(3), 713–728 (2005)
  * [11] Chekuri, C., Vondrák, J., Zenklusen, R.: Dependent randomized rounding via exchange properties of combinatorial structures. In: 2010 IEEE 51st Annual Symposium on Foundations of Computer Science. pp. 575–584. IEEE (2010)
  * [12] Chekuri, C., Vondrák, J., Zenklusen, R.: Multi-budgeted matchings and matroid intersection via dependent rounding. In: Proc. SODA. pp. 1080–1097 (2011)
  * [13] Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to algorithms. MIT press (2022)
  * [14] Cygan, M., Mucha, M., Wegrzycki, K., WIodarczyk, M.: On problems equivalent to (min,+)-convolution. ACM Transactions on Algorithms (TALG) 15(1), 1–25 (2019)
  * [15] Doron-Arad, I., Kulik, A., Shachnai, H.: An FPTAS for budgeted laminar matroid independent set. Operations Research Letters 51
  * [16] Doron-Arad, I., Kulik, A., Shachnai, H.: An afptas for bin packing with partition matroid via a new method for lp rounding. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Schloss-Dagstuhl-Leibniz Zentrum für Informatik (2023)
  * [17] Doron-Arad, I., Kulik, A., Shachnai, H.: Budgeted matroid maximization: a parameterized viewpoint. IPEC (2023)
  * [18] Doron-Arad, I., Kulik, A., Shachnai, H.: An EPTAS for budgeted matching and budgeted matroid intersection via representative sets. In: Proc. ICALP. pp. 49:1–49:16 (2023)
  * [19] Doron-Arad, I., Kulik, A., Shachnai, H.: An EPTAS for budgeted matroid independent set. In: Proc. SOSA. pp. 69–83 (2023)
  * [20] Edmonds, J.: Minimum partition of a matroid into independent subsets. J. Res. Nat. Bur. Standards Sect. B 69, 67–72 (1965)
  * [21] Fomin, F.V., Golovach, P.A., Korhonen, T., Simonov, K., Stamoulis, G.: Fixed-parameter tractability of maximum colored path and beyond. In: Proc. SODA. pp. 3700–3712 (2023)
  * [22] Garey, M.R.: Computers and intractability: A guide to the theory of np-completeness, freeman. Fundamental (1997)
  * [23] Grage, K., Jansen, K., Klein, K.M.: An eptas for machine scheduling with bag-constraints. In: The 31st ACM Symposium on Parallelism in Algorithms and Architectures. pp. 135–144 (2019)
  * [24] Grandoni, F., Zenklusen, R.: Approximation schemes for multi-budgeted independence systems. In: Proc. ESA. pp. 536–548 (2010)
  * [25] Hassin, R., Levin, A.: An efficient polynomial time approximation scheme for the constrained minimum spanning tree problem using matroid intersection. SIAM Journal on Computing 33(2), 261–268 (2004)
  * [26] Hong, S.P., Chung, S.J., Park, B.H.: A fully polynomial bicriteria approximation scheme for the constrained spanning tree problem. Operations Research Letters 32(3), 233–239 (2004)
  * [27] Jensen, P.M., Korte, B.: Complexity of matroid property algorithms. SIAM Journal on Computing 11(1), 184–190 (1982)
  * [28] Karp, R.M., Upfal, E., Wigderson, A.: The complexity of parallel computation on matroids. In: 26th Annual Symposium on Foundations of Computer Science (sfcs 1985). pp. 541–550. IEEE (1985)
  * [29] Kulik, A., Shachnai, H.: There is no eptas for two-dimensional knapsack. Information Processing Letters 110(16), 707–710 (2010)
  * [30] Lawler, E.L.: Matroid intersection algorithms. Mathematical programming 9(1), 31–56 (1975)
  * [31] Lawler, E.L.: Fast approximation algorithms for knapsack problems. Math. Oper. Res. 4(4), 339–356 (1979)
  * [32] Lovász, L.: The matroid matching problem. Algebraic methods in graph theory 2, 495–517 (1978)
  * [33] Oxley, J.G.: Matroid theory, vol. 3. Oxford University Press, USA (2006)
  * [34] Pendavingh, R., Van der Pol, J.: On the number of matroids compared to the number of sparse paving matroids. arXiv preprint arXiv:1411.0935 (2014)
  * [35] Ravi, R., Goemans, M.X.: The constrained minimum spanning tree problem. In: Algorithm Theory—SWAT’96: 5th Scandinavian Workshop on Algorithm Theory Reykjavík, Iceland, July 3–5, 1996 Proceedings 5. pp. 66–75. Springer (1996)
  * [36] Schrijver, A.: Combinatorial optimization: polyhedra and efficiency, vol. 24. Springer (2003)
  * [37] Sinha, P., Zoltners, A.A.: The multiple-choice knapsack problem. Operations Research 27(3), 503–515 (1979)
  * [38] Soto, J.A.: A simple ptas for weighted matroid matching on strongly base orderable matroids. Discrete Applied Mathematics 164, 406–412 (2014)
  * [39] Sviridenko, M.: A note on maximizing a submodular set function subject to a knapsack constraint. Operations Research Letters 32(1), 41–43 (2004)