# Accelerating Matroid Optimization through
Fast Imprecise Oracles

Franziska Eberle Institute of Mathematics, Technical University of Berlin,
Germany<EMAIL_ADDRESS>Felix Hommelsheim Faculty of Mathematics and
Computer Science, University of Bremen, Germany.
<EMAIL_ADDRESS>Alexander
Lindermayr22footnotemark: 2 Zhenwei Liu Faculty of Mathematics and Computer
Science, University of Bremen, Germany, and Zhejiang University, China.
<EMAIL_ADDRESS>Nicole Megow22footnotemark: 2 Jens
Schlöter22footnotemark: 2

###### Abstract

Querying complex models for precise information (e.g. traffic models, database
systems, large ML models) often entails intense computations and results in
long response times. Thus, weaker models which give imprecise results quickly
can be advantageous, provided inaccuracies can be resolved using few queries
to a stronger model. In the fundamental problem of computing a maximum-weight
basis of a matroid, a well-known generalization of many combinatorial
optimization problems, algorithms have access to a _clean_ oracle to query
matroid information. We additionally equip algorithms with a fast but _dirty_
oracle modelling an unknown, potentially different matroid. We design and
analyze practical algorithms which only use few clean queries w.r.t. the
quality of the dirty oracle, while maintaining robustness against arbitrarily
poor dirty matroids, approaching the performance of classic algorithms for the
given problem. Notably, we prove that our algorithms are, in many respects,
best-possible. Further, we outline extensions to other matroid oracle types,
non-free dirty oracles and other matroid problems.

##  1 Introduction

Matroids play a central and unifying role in combinatorial optimization as
numerous classical problems can be formulated as matroid basis problems and
they find application, e.g., in resource allocation and network design.
Moreover, matroids precisely characterize structures for which the greedy
algorithm efficiently computes an optimal solution for linear (and more
general) objective functions.

A _matroid_ $\mathcal{M}=(E,\mathcal{I})$ is a set system with a certain
augmentation property that is represented by a ground set $E$ of elements and
a family $\mathcal{I}\subseteq 2^{E}$ of _independence_ sets; we give formal
definitions later. Since $|\mathcal{I}|$ can be exponential in $n:=|E|$,
algorithms operating on matroids are usually given access to _oracles_ via
_queries_. The _independence oracle_ answers for a query $S\subseteq E$
whether $S\in\mathcal{I}$. A _basis_ of a matroid is an independent set of
maximum cardinality.

In the most fundamental matroid optimization problem, we are given a matroid
$\mathcal{M}=(E,\mathcal{I})$ and weights $w_{e}$ for every element $e\in E$,
and have to find a basis $B$ of maximum weight $\sum_{e\in B}w_{e}$. In his
seminal work, Edmonds [16] showed that this problem can be solved efficiently
by the _greedy algorithm_ , and, vice versa, that matroids are the most
general downward-closed set systems for which this algorithm is correct. The
greedy algorithm iteratively adds elements in non-increasing order of their
weight to the solution if possible; hence, it requires $n$ (independence)
oracle calls. It is also not hard to see that, in general, one needs at least
$n$ oracle calls. More general matroid problems include matroid intersection
and matroid partition; we omit details.

Depending on the specific matroid, the oracle’s task of evaluating an
independence query might be highly complex, demanding significant
computational effort. Consequently, substantial research efforts aim for
algorithms that minimize the number of oracle calls required; see, e.g., [8,
5, 36].

In many methods in practice, such as those employed in machine learning
pipelines or heuristic approaches, it is common to incorporate an efficient
yet less precise model in addition to the precise but computationally
expensive oracle model. Examples of less precise oracles include a neural
network trained on potentially noisy data, or a fast heuristic designed for a
simplified independence system that encompasses only a subset of the elements.
More concretely, imagine a network problem in which an independence oracle
shall evaluate, for a given set of edges, whether they contain a cycle
(graphic matroid). While this is doable in time linear in the set size, it
might become prohibitively expensive for huge input sets. In such cases, a
trained model giving an inaccurate answer, or a heuristic applied to a
truncated much smaller backbone subnetwork could be used to efficiently yield
a potentially imprecise answer.

We initiate the study of the following two-oracle model for matroid problems:
In addition to the “expensive” precise (we say _clean_) independence oracle of
a given matroid $\mathcal{M}$, we assume that an algorithm has access to a
fast imprecise (we say _dirty_) independence oracle. We assume that this
oracle is the independence oracle of a hidden _dirty_ matroid
$\mathcal{M}_{d}$. In the most basic setup, we assume that queries to the
dirty oracle come for free and that the algorithm has no knowledge about how
$\mathcal{M}_{d}$ relates to the _clean_ matroid $\mathcal{M}$.

In this paper, we address the following questions, focusing on the problem of
finding a maximum-weight matroid basis and exploring more general matroid
problems:

  * •

_Can we (optimally) utilize a dirty matroid to reduce the clean oracle calls,
possibly depending on its precision?_

  * •

_Can we (nearly) match the performance of the greedy algorithm despite a low-
quality dirty matroid?_

Our work also aligns with the celebrated framework of _learning-augmented
algorithms_ [30, 29], which is receiving tremendous attention. Here,
typically, an algorithm has access to a problem-specific _prediction_ and
yields good results when the prediction is accurate (_consistency_) and does
not perform too bad when given arbitrary predictions (_robustness_). Ideally,
the performance degrades smoothly with the prediction’s quality, measured by
an _error_ function. In our most basic model, queries to the dirty oracle are
at no cost. Hence, a basis of the dirty matroid can be computed for free, and
equivalently we may assume that an algorithm is given a dirty matroid basis as
a possibly imprecise prediction.

###  1.1 Our Results

We answer the above questions to the affirmative. We present an algorithm
which computes, given access to a dirty matroid, a maximum-weight basis
significantly faster than the greedy algorithm whenever the dirty matroid is
of good quality, while maintaining an almost optimal worst-case guarantee at
any time.

######  Theorem 1.1.

For any integer $k\geq 1$, there is an algorithm which, given a dirty matroid
$\mathcal{M}_{d}$ of rank $r_{d}$ with unknown quality indicators $\eta_{A}$
and $\eta_{R}$, computes a maximum-weight basis of a matroid $\mathcal{M}$ of
rank $r$ with at most

$\min\left\\{n-r+k+\eta_{A}\cdot(k+1)+\eta_{R}\cdot(k+1)\lceil\log_{2}r_{d}\rceil,\;\left(1+\frac{1}{k}\right)n\right\\}$

many oracle calls to $\mathcal{M}$.

In particular, the bound smoothly degrades w.r.t. the quality of the dirty
matroid, measured by our error measures $\eta_{A}$ and $\eta_{R}$.
Intuitively, $\eta_{A}$ and $\eta_{R}$ denote the number of elements that have
to be added to/removed from a maximum-weight basis of the dirty matroid to
reach a maximum-weight clean basis; we give a formal definition later.
Moreover, our algorithm has a tuning parameter $k$ with which we can regulate
the level of robustness against a dirty matroid of bad quality; a beneficial
feature when the quality of the dirty matroid can be roughly estimated.

In the case of unit weights, we achieve the same result with an improved one-
to-one dependence on $\eta_{A}$ (compared to $k+1$ above). In particular, when
ignoring robustness ($k=0$), we design an algorithm for the unit-weight
setting which uses at most
$n-r+1+\eta_{A}+\eta_{R}\cdot\lceil\log_{2}r_{d}\rceil$ many clean oracle
calls. To separate the unit-weight case, we prove that no deterministic
algorithm can achieve such a bound for the case of arbitrary weights.
Moreover, we prove that this bound is essentially best-possible for any
deterministic algorithm, even if it knows $\eta_{A}$ and $\eta_{R}$ upfront.
In particular, we show that any algorithm requires at least $n-r+1$ clean
oracle calls and has at least our dependency on $\eta_{A}$ and a logarithmic
dependency on $\eta_{R}$.

##### Extensions

In Section 4, we develop several extensions of our main results. First, we
show that access to a more powerful clean rank oracle (see Section 4.1 for the
definition) can improve our algorithmic results in the unweighted case to at
most
$\min\\{\min\\{\eta_{A}\cdot\lceil\log_{2}(n-r_{d})\rceil,n-r_{d}\\}+2+\eta_{R}\cdot\lceil\log_{2}r_{d}\rceil,n+1\\}$
clean oracle calls. Then, we discuss different algorithms and challenges in
the more general setting, where queries to the dirty oracle also incur a cost
and the objective is to minimize the total query cost. Finally, we give an
outlook on using the two-oracle model for the matroid intersection problem;
see Section 4.3 for the definition. We show how to implement our techniques
into the classic textbook algorithm for matroid intersection.

###  1.2 Further Related Work

##### Noisy Oracles, Two-Oracle Model, Imprecise Predictions

Optimization in the presence of noisy or imprecise oracles is a fundamental
problem and has been studied extensively, also for submodular optimization
[26, 24, 23, 25, 35] which is connected to matroid optimization via the
submodularity of rank functions. Previous work nearly exclusively studies
problems with access only to a _noisy (weak, dirty)_ oracle, where the noise
usually is of stochastic nature. In many applications however, the usage of
two oracles, one weak (dirty) and one strong (clean), is not uncommon.
Examples include ML pipelines combining efficient but less precise models with
expensive but more accurate ones [27, 28], data labeling [37, 38] and
applications in correlation clustering [34]. Despite its practical relevance,
a two-oracle model that takes both, a weak fast and a precise slow/expensive
oracle into account has hardly been investigated from a theoretical point of
view with two very recent exceptions [1, 4]. Bai and Coester [1] consider
sorting with a clean and a dirty comparison operator. They aim at minimizing
the number of clean comparison operator calls and give guarantees that
smoothly degrade with the number of wrong dirty comparison answers. Bateni et
al. [4] consider the Minimum Spanning Tree (MST) problem (and clustering) in
metric spaces that can be accessed via strong and weak oracles. In contrast to
our model, they consider oracles for accessing the distance between two points
and not for deciding cycle freeness (graphic matroid). Besides these explicit
results on two-oracle models, explorable uncertainty with predictions [19, 18]
can also be interpreted as such a model.

##### Two- and Multistage Problems

All algorithms presented in this paper also solve the following two-stage
problem: Given a maximum-weight basis $B$ for a first-stage matroid
$\mathcal{M}_{d}$ (dirty matroid), compute a maximum-weight basis $B^{\prime}$
for a second stage matroid $\mathcal{M}$ (clean matroid) with minimum
$|B\triangle B^{\prime}|$, where $B\triangle B^{\prime}$ denotes the symmetric
difference of $B$ and $B^{\prime}$, and minimize the number of oracle calls to
$\mathcal{M}$. Two- (or multi-) stage problems of this type have been studied
extensively, mostly for graph problems [32, 12, 2, 3, 11, 20, 21, 17] but also
for matroids [13, 22, 7, 6]. Most of these works consider a combined objective
for the quality of the second stage solution and the distance between the
first and second stage solutions. In contrast, we insist on an optimal second
stage solution and minimize the number of clean oracle calls.

###  1.3 Preliminaries

A _matroid_ $\mathcal{M}$ is a tupel $(E,\mathcal{I})$ consisting of a finite
ground set $E$ of $n$ elements and a family of _independent sets_
$\mathcal{I}\subseteq 2^{E}$ with $\emptyset\in\mathcal{I}$ that satisfy the
following properties: (i) $\mathcal{I}$ is downward-closed, i.e.,
$A\in\mathcal{I}$ implies $B\in\mathcal{I}$ for all $B\subseteq A$ and (ii) if
$A,B\in\mathcal{I}$ with $|A|>|B|$, then there exists $a\in A\setminus B$ s.t.
$B+a\in\mathcal{I}$. (We write $X+e$ when we add $e\in E\setminus X$ to
$X\subseteq E$ and $X-e$ when we remove $e\in X$ from $X\subseteq E$.) An
important notion are _bases_ , which are the (inclusion-wise) maximal elements
of $\mathcal{I}$; for a fixed matroid, we denote the set of bases by
$\mathcal{B}$. For a dirty matroid $\mathcal{M}_{d}$, we refer to the set of
bases by $\mathcal{B}_{d}$. A _circuit_ is a minimal dependent set of
elements. The main results of this paper consider the problem of finding a
maximum-weight basis, i.e., given matroid $\mathcal{M}=(E,\mathcal{I})$ and
weights $w_{e}$ for all $e\in E$, the goal is to find a basis
$B\in\mathcal{B}$ maximizing $\sum_{e\in B}w_{e}$. In this context, we always
assume that the elements of $E=\\{e_{1},\ldots,e_{n}\\}$ are indexed according
to the weight order, i.e., $i\leq j$ implies $w_{e_{i}}\geq w_{e_{j}}$, with
ties broken arbitrarily. Given that, for any $i$ and $S\subseteq E$ we define
$S_{\leq i}=\\{e_{j}\in S\mid j\leq i\\}$ ($S_{\geq i}$ analogously).

##### Requirements on Algorithms and Optimal Solutions

For all problems considered in this paper, we require algorithms to execute
clean queries (oracle calls) until the answers to these queries reveal
sufficient information to solve the given problem, e.g., find a maximum-weight
basis for the clean matroid. More precisely, the queries executed by the
algorithm together with the answers must be a _certificate_ that a third party
with only access to the clean matroid and without any additional knowledge can
use in order to find a provable solution. In particular, an optimal algorithm
that knows the answers to all clean queries upfront has to execute queries in
order to satisfy the certificate requirement.

##### Definition of our Error Measure

We define an error measure that quantifies the quality of the dirty oracle
w.r.t. the clean oracle. Let $\mathcal{B}^{*}$ be the set of maximum-weight
bases of $\mathcal{M}$ and $\mathcal{B}^{*}_{d}$ be the set of maximum-weight
bases of $\mathcal{M}_{d}$. (In the unweighted case,
$\mathcal{B}^{*}=\mathcal{B}$ and $\mathcal{B}_{d}^{*}=\mathcal{B}_{d}$.) We
first define for every $S\in\mathcal{B}^{*}_{d}$ the sets $A(S),R(S)$ as the
(in total) cardinality-wise smallest sets $A\subseteq E\setminus S$ and
$R\subseteq S$ such that $S\cup A\setminus R\in\mathcal{B}^{*}$. These sets
describe the smallest number of modifications necessary to transform $S$ into
a maximum-weight basis of $\mathcal{M}$, where specifically $R(S)$ are the
elements to be _removed_ and $A(S)$ are the elements to be _added_. We call
$\lvert A(S)\rvert+\lvert R(S)\rvert$ the _modification distance_ from $S$ to
$\mathcal{B}^{*}$. Our final error measure is defined as the largest
modification distance of any maximum-weight basis of $\mathcal{M}_{d}$, that
is, if $\bm{\hat{}}{S}\in\mathcal{B}_{d}^{*}$ maximizes $\lvert
A(\bm{\hat{}}{S})\rvert+\lvert R(\bm{\hat{}}{S})\rvert$, then we define
$\eta_{A}=\lvert A(\bm{\hat{}}{S})\rvert$ and $\eta_{R}=\lvert
R(\bm{\hat{}}{S})\rvert$.

In the proofs of our error-dependent algorithmic guarantees we will exploit
the following observation.

######  Observation 1.2.

For all $S_{1},S_{2}\in\mathcal{B}_{d}$, $\lvert A(S_{1})\rvert\leq\lvert
A(A_{2})\rvert\Leftrightarrow\lvert R(S_{1})\rvert\leq\lvert R(S_{2})\rvert$
and $\lvert A(S_{1})\rvert\leq\eta_{A}$ and $\lvert
R(S_{2})\rvert\leq\eta_{R}$. This also holds if we replace $\mathcal{B}_{d}$
with $\mathcal{B}_{d}^{*}$.

###  1.4 Discussion of the Model

For all our results on computing a (maximum-weight) basis, it suffices to
first compute a (maximum-weight) dirty basis and afterwards switch to
exclusively using the clean oracle. A similar observation can be made for the
results of Bai and Coester [1] on sorting, where it would be possible to
initially compute a tournament graph for the dirty comparator and afterwards
switch to only using the clean comparator, without increasing the number of
clean comparator calls. In Section 4, we observe that separating the usage of
the dirty and clean oracles in this way does not work anymore if dirty oracle
calls also incur costs.

Bai and Coester [1] use the number of wrong dirty comparator answers as error
measure. While this is a meaningful error measure for sorting, a similar error
measure for our problem does not seem to accurately capture the quality of the
dirty oracle. Consider an instance with unit weights, where we have
$\mathcal{B}_{d}\subset\mathcal{B}$. This can lead to an exponential number of
wrong dirty oracle answers, but the dirty oracle still allows us to compute a
clean basis. For this reason, we use the modification distance as error
measure instead.

##  2 Warm-up: Computing an Unweighted Basis

Consider the basic problem of finding any basis of a matroid. The goal of this
section is to give a gentle introduction to our algorithmic methods, which we
extend to the weighted setting in the next section. Note that without the
dirty oracle, we need exactly $n$ clean oracle calls to find and verify any
basis in the worst-case. In the following, we assume that we are given an
arbitrary basis $B_{d}$ of the dirty matroid $\mathcal{M}_{d}$, which can be
computed without any call to the clean oracle.

###  2.1 A Simple Algorithm without Error Dependency

We analyze the following algorithm, called the _simple algorithm_ : First, if
$B_{d}\in\mathcal{I}$, we set $B$ to $B_{d}$. Otherwise, we set $B$ to the
empty set. Then for each element $e\in E\setminus B$, we add it to $B$ if
$B+e\in\mathcal{I}$ and output $B$ at the end.

The idea of the simple algorithm is to only use the dirty basis $B_{d}$ if it
is independent in the clean matroid, as we then can easily augment it to a
clean basis. Otherwise, we abandon it and effectively run the classic greedy
algorithm.

######  Lemma 2.1.

The simple algorithm computes a clean basis using at most $n+1$ clean oracle
calls. Further, if $B_{d}\in\mathcal{B}$, it terminates using at most $n-r+1$
clean oracle calls.

###### Proof.

The correctness follows easily from matroid properties. If the dirty oracle is
perfectly correct, i.e. $B_{d}\in\mathcal{B}$, then we only need to use one
clean oracle call to check whether $B_{d}\in\mathcal{I}$ and $n-r$ calls for
checking the maximality. If $B_{d}\notin\mathcal{I}$, we start from the empty
set and check whether to add each of the $n$ elements. Thus, the algorithm
uses at most $n+1$ clean oracle calls in any case. ∎

In Section 2.4, we will see that, surprisingly, this simple algorithm achieves
a best-possible trade-off between optimizing the cases $B_{d}\in\mathcal{B}$
and $B_{d}\notin\mathcal{B}$ at the same time.

###  2.2 An Error-Dependent Algorithm

The simple algorithm abandons the dirty basis $B_{d}$ if it is not independent
in $\mathcal{M}$. However, in some cases removing a single element from
$B_{d}$ leads to independence, e.g., if $B_{d}$ is a circuit, then the simple
algorithm seems very wasteful. This seems particularly drastic if the clean
and dirty oracle are relatively “close”, i.e., the error measured by the
modification distance is small. This suggests a refinement with a more careful
treatment of the dirty basis $B_{d}$. We propose a binary search strategy to
remove elements from $B_{d}$ until it becomes independent. A key feature is
that this allows for an error-dependent performance guarantee bounding the
number of clean oracle calls by $\eta_{A}$ and $\eta_{R}$, the smallest
numbers of elements to be added and removed to make a dirty basis a basis of
the clean matroid.

We define the _error-dependent algorithm_ : First, set $B$ to $B_{d}$ and fix
some order of the elements in $B$. Until $B\in\mathcal{I}$ we repeatedly use
binary search to find the smallest index $i$ s.t. $B_{\leq
i}\notin\mathcal{I}$, and then remove $e_{i}$ from $B$. Then, once
$B\in\mathcal{I}$, for each element $e\in E\setminus B_{d}$, we add it to $B$
if $B+e\in\mathcal{I}$ and output $B$ at the end.

######  Lemma 2.2.

The error-dependent algorithm computes a clean basis using at most
$n-r+1+\eta_{A}+\eta_{R}\cdot\lceil\log_{2}r_{d}\rceil$ clean oracle calls.

###### Proof.

The algorithm simulates finding a maximal independent subset of $B_{d}$ w.r.t.
the clean matroid, and augments the resulting set to a clean basis. Hence, the
correctness follows from matroid properties. By 1.2, we remove $\lvert
R(B_{d})\rvert\leq\eta_{R}$ elements from $B_{d}$. Hence, the removal loop is
executed $\lvert R(B_{d})\rvert$ times. In each iteration, we use at most
$1+\lceil\log_{2}r_{d}\rceil$ clean queries (one for checking
$B\in\mathcal{I}$ and at most $\lceil\log_{2}r_{d}\rceil$ for the binary
search). Thus, the removing process uses at most $\lvert
R(B_{d})\rvert(1+\lceil\log_{2}r_{d}\rceil)$ clean queries. Augmenting $B$
uses $n-r_{d}$ clean queries. Combined, our algorithm uses at most $\lvert
R(B_{d})\rvert(1+\lceil\log_{2}r_{d}\rceil)+n-r_{d}+1$ oracle calls. We
conclude using $\lvert R(B_{d})\rvert\leq\eta_{R}$ and
$r=r_{d}-\eta_{R}+\eta_{A}$. ∎

###  2.3 An Error-Dependent and Robust Algorithm

The error-dependent algorithm has a good bound on the number of clean oracle
calls (less than $n$) when $\eta_{A}$ and $\eta_{R}$ are small. However, in
terms of _robustness_ , i.e., the maximum number of oracle calls for any
instance, this algorithm is asymptotically worse than the gold standard of
$n$, achieved by the classic greedy algorithm. This is the case when the dirty
basis is equal to $E$, but the clean matroid is empty: the error-dependent
algorithm executes $n$ binary searches over narrowing intervals, using
$\log_{2}(n!)\in\Theta(n\log n)$ clean oracle calls. By looking closer at the
error-dependent algorithm, the special structure of this example can be
explained because queries charged to $n-r+\eta_{A}$ are essentially also done
by the greedy algorithm. Hence, they are in a sense already robust. Motivated
by the greedy algorithm, another extreme variant of the removal process would
be to go linearly through $B_{d}$ and greedily remove elements. This gives an
optimal robustness, but is clearly bad if $\eta_{R}$ is small.

For our main result in the unweighted setting, we combine both extremes and
achieve a trade-off using the following key observation. If we have to remove
many elements ($\eta_{R}$ is large), some elements must be close to each
other. In particular, if the next removal is close to the last one (in terms
of the fixed total order), a linear search costs less than a binary search.
Based on this, after a removal, we first check the next $\Theta(\log(r_{d}))$
elements of $B_{d}$ linearly for other removals before executing a binary
search. This bounds the number of binary searches by
$\Theta(\frac{r_{d}}{\log(r_{d})})$, each incurring a cost of
$\lceil\log_{2}(r_{d})\rceil$. However, the linear search also incurs some
cost. Thus, we further parameterize this idea with a parameter $k$ which
measures the trade-off between linear searches and binary searches.

The formal description of this algorithm is given in Algorithm 1. Note that
each linear search has two parts (Line 5 and Line 12). Between the two parts,
we insert a check $B\in\mathcal{I}$ (Line 9), which is necessary to prevent
using too many queries when there are no further removals necessary. A small
detail here is that we only have to do this check if there actually are
elements to check in the second part (which is not the case if $|S|\leq k-1$).

Algorithm 1 Find a Basis (robustified)

0: dirty basis $B_{d}$, matroid $\mathcal{M}=(E,\mathcal{I})$, integer $k\geq
1$

0: basis $B$ of $\mathcal{M}$

1: $B\leftarrow\emptyset$ and $S\leftarrow B_{d}$

2: Fix an order for $S=\\{e_{1},\ldots,e_{r_{d}}\\}$

3: while $S\neq\emptyset$ do

4: Re-index the elements in $S$ from $1$ to $|S|$, keeping the relative order.

5: Find the smallest index $i\in\\{1,\ldots,\min\\{|S|,k-1\\}\\}$ with $B\cup
S_{\leq i}\notin\mathcal{I}$ via _linear search_.

6: if such an $i$ exists then

7: $B\leftarrow B\cup S_{\leq i-1}$ and $S\leftarrow S\setminus S_{\leq i}$
and go to next iteration of Line 3.

8: end if

9: if $|S|\leq k-1$ or $B\cup S\in\mathcal{I}$ then

10: $B\leftarrow B\cup S$ and $S\leftarrow\emptyset$ and go to next iteration
of Line 3.

11: end if

12: Find the smallest index
$i\in\\{k,\ldots,\min\\{k\lceil\log_{2}r_{d}\rceil,|S|\\}\\}$ with $B\cup
S_{\leq i}\notin\mathcal{I}$ via _linear search_.

13: if there is no such index $i$ then

14: Find the smallest index
$i\in\\{k\lceil\log_{2}r_{d}\rceil+1,\ldots,|S|\\}$ with $B\cup S_{\leq
i}\notin\mathcal{I}$ via _binary search_ (guaranteed to exist).

15: end if

16: $B\leftarrow B\cup S_{\leq i-1}$ and $S\leftarrow S\setminus S_{\leq i}$

17: end while

18: for $e\in E\setminus B_{d}$ do

19: if $B+e\in\mathcal{I}$ then

20: $B\leftarrow B+e$

21: end if

22: end for

23: output $B$

We now prove the main result of this section.

######  Theorem 2.3.

For any integer $k\geq 1$, given a dirty matroid $\mathcal{M}_{d}$ of rank
$r_{d}$ with unknown quality indicators $\eta_{A}$ and $\eta_{R}$, Algorithm 1
computes a basis of a matroid $\mathcal{M}$ of rank $r$ with at most

$\min\left\\{n-r+k+\eta_{A}+\eta_{R}\cdot(k+1)\lceil\log_{2}r_{d}\rceil,\,\left(1+\frac{1}{k}\right)n\right\\}$

many oracle calls to $\mathcal{M}$.

###### Proof.

Observe that the algorithm finds a maximal independent subset of $B_{d}$ in
the clean matroid and greedily tries to add all remaining elements, similar to
the error-dependent algorithm. Hence, the correctness follows as in the proof
of Lemma 2.2.

It remains to bound the number of clean oracle calls. We first prove the
error-dependent upper bound. Note that the algorithm removes
$|R(B_{d})|\leq\eta_{R}$ elements from $B_{d}$, and then adds
$|A(B_{d})|\leq\eta_{A}$ elements by 1.2. For every removed element, the
algorithm uses at most $k\lceil\log_{2}r_{d}\rceil$ clean oracle calls due to
the two linear searches, $\lceil\log_{2}r_{d}\rceil$ calls in the binary
search, and one extra query for the check between the two linear searches.
Once we have a solution $B\cup S$ that is not necessarily maximum but
feasible, which we do not know yet, we need to use at most $k$ additional
queries until we verify that this solution is indeed feasible: We have up to
$k-1$ queries of linear search in Line 5 and one query in Line 9. After
removing elements, the algorithm makes $n-r_{d}$ queries in Line 19. Thus, the
total number of clean oracle calls is at most
$|R(B_{d})|((k+1)\lceil\log_{2}r_{d}\rceil+1)+n-r_{d}$. By plugging in
$r_{d}-\eta_{R}+\eta_{A}=r$, we proof the stated upper bound of

$n-r+k+\eta_{A}+\eta_{R}(k+1)\lceil\log_{2}r_{d}\rceil.$

Second, we prove the robust upper bound that is independent of $\eta_{A}$ and
$\eta_{R}$. To this end, we partition $B_{d}=\\{e_{1},\ldots,e_{r_{d}}\\}$
into segments separated by the removed elements. Each segment (except the last
one, which we treat separately below) contains exactly one removed element at
the end. If a linear search (Lines 5 and 12) finds the element to be removed,
we call the corresponding segment _short_. Otherwise, we say it is  _long_.

Let the total length of short segments be $L_{\text{short}}$. The cost of a
short segment is equal to its length, plus one for the check between the two
linear searches in Line 9 if its length is at least $k$. Thus, the total cost
of all short segments is at most $(1+\frac{1}{k})L_{\text{short}}$.

Let the total length of long segments be $L_{\text{long}}$. In a long segment,
there are exactly $k\lceil\log_{2}r_{d}\rceil$ queries done by the linear
searches (Lines 5 and 12), one query due to Line 9 and at most
$\lceil\log_{2}r_{d}\rceil$ many queries by the binary search in Line 14.
Thus, the total cost of a long segment is at most
$(k+1)\lceil\log_{2}r_{d}\rceil+1$. Moreover, there can be at most
$\frac{L_{\text{long}}}{k\lceil\log_{2}r_{d}\rceil+1}$ many long segments.
Therefore, the total cost of all long segments is at most
$(1+\frac{1}{k})L_{\text{long}}$.

Finally, let $L_{\text{last}}$ be the length of the last segment, where no
elements are removed. If this does not exist we set $L_{\text{last}}=0$. When
the algorithm considers this segment, the condition that $B\cup
S\in\mathcal{I}$ in Line 9 is true because no further elements are removed
afterwards. Regarding the other condition in Line 9, there are two cases. If
$|S|\leq k-1$, then we do not query $B\cup S\in\mathcal{I}$ and terminate the
while-loop. Before that, we use exactly $L_{\text{last}}$ many oracle calls in
Line 7. Otherwise, that is $|S|\geq k$, we use $k-1$ oracle calls in Line 7
and one query in Line 9, which evaluates true and terminates the while-loop.
Since $k\leq|S|\leq L_{\text{last}}$, we conclude that in both cases we use at
most $L_{\text{last}}$ many oracle calls during the last segment.

Therefore, the total number of queries done in Lines 3 to 17 is at most

$\left(1+\frac{1}{k}\right)(L_{\text{short}}+L_{\text{long}})+L_{\text{last}}\leq\left(1+\frac{1}{k}\right)r_{d}.$

Together with the $n-r_{d}$ oracle calls in Line 19, we conclude that the
total number of oracle calls is at most

$n-r_{d}+\left(1+\frac{1}{k}\right)r_{d}\leq\left(1+\frac{1}{k}\right)n.$

This concludes the proof of Theorem 2.3. ∎

###  2.4 Lower Bounds

To conclude this section, we complement our upper bounds with lower bounds on
the worst-case number of clean queries required by any deterministic
algorithm. First, we show that, even if $\mathcal{M}=\mathcal{M}_{d}$, the
worst-case number of clean queries is at least $n-r+1$. The following lemma
also shows that this best-possible number of queries for instances with
$\mathcal{M}=\mathcal{M}_{d}$ and the best-possible worst-case bound of $n$
queries cannot be achieved at the same time.

######  Lemma 2.4.

For every rank $r\geq 1$, no deterministic algorithm can use less than $n-r+1$
clean queries, even if $\mathcal{M}=\mathcal{M}_{d}$. Further, for any
algorithm which uses exactly $n-r+1$ clean queries whenever
$\mathcal{M}=\mathcal{M}_{d}$, there is at least one instance where it uses at
least $n+1$ clean queries.

###### Proof.

Consider arbitrary $n$ and $r$ with $1\leq r\leq n$. We give a clean matroid
$\mathcal{M}$ such that the statement of the lemma holds for the instance
defined by $\mathcal{M}$ and the dirty matroid $\mathcal{M}_{d}=\mathcal{M}$.
Let $E=\\{e_{1},\ldots,e_{n}\\}$ denote the ground set of elements. We define
$\mathcal{M}=\mathcal{M}_{d}$ as a partition matroid with two classes of
elements $C_{1}=\\{e_{1},\ldots,e_{r-1}\\}$ and
$C_{2}=\\{e_{r},\ldots,e_{n}\\}$. Each set $S\subseteq E$ with $|S\cap
C_{1}|\leq r-1$ and $|S\cap C_{2}|\leq 1$ is independent in
$\mathcal{M}=\mathcal{M}_{d}$, and we denote the set of independent sets by
$\mathcal{I}$ and the set of bases by $\mathcal{B}$. Each basis of this
matroid completely contains $C_{1}$ and exactly one member of $C_{2}$. Thus,
the rank of $\mathcal{M}$ is indeed $r$. We show that even if the algorithm
knows that the underlying matroid is a partition matroid (but it does not know
the exact classes), it needs at least $n-r+1$ queries.

As we require algorithms to show some certificate for a clean basis (see
Section 1.3), every feasible algorithm has to verify that (i) some
$B\in\mathcal{B}_{d}=\mathcal{B}$ is independent in $\mathcal{M}$ and that
(ii) $B\cup\\{e\\}$ is not independent in $\mathcal{M}=\mathcal{M}_{d}$ for
every $e\in E\setminus B$.

Consider the instance defined above. To prove (i), an algorithm _has to_ make
the oracle call $B\in\mathcal{I}$ as calls to supersets of $B$ will return
false and calls to sets $A$ with $B\not\subseteq A$ cannot prove that $B$ is
independent.

Let $e$ denote the element of $C_{2}$ that is part of the basis $B$ selected
by the algorithm. To prove (ii), the algorithm has to verify that the elements
$\\{e_{r},\ldots,e_{n}\\}\setminus\\{e\\}$ are all part of the same class as
$e$ and that this class has capacity one. Otherwise, the queries by the
algorithm would not reveal sufficient information to distinguish between the
matroid $\mathcal{M}$ and a potential alternative matroid
$\mathcal{M}^{\prime}$ that has a third class with capacity one. However, as
$B$ would not be a basis for $\mathcal{M}^{\prime}$, the queries by the
algorithm must reveal sufficient information to distinguish $\mathcal{M}$ and
$\mathcal{M}^{\prime}$.

To prove that an element $e^{\prime}$ is part of the same class as $e$, an
algorithm has to execute a query $A\in\mathcal{I}$ with $A\cap
C_{2}=\\{e^{\prime},e^{\prime\prime}\\}$ for an element $e^{\prime\prime}$
that is already known to be in the same class as $e$. This is because queries
$A\in\mathcal{I}$ with either $|A\cap C_{2}|=1$, $|A\cap C_{2}|\geq 3$ or
$e^{\prime}\not\in A$ would always give the same answer even for the potential
alternative matroid $\mathcal{M}^{\prime}$ in which $e^{\prime}$ forms a class
of capacity one on its own.

In total, this leads to at least $n-r+1$ oracle calls. Further, consider the
robustness case that the algorithm is given an instance with a dirty matroid
as described above and a clean matroid whose only independent set is the empty
set. By the above arguments, in order to use only $n-r+1$ queries for the case
$\mathcal{M}=\mathcal{M}_{d}$, the algorithm has to query some $B\in B_{d}$.
But this query does not help the algorithm to find out that the only clean
basis is the empty set, i.e., it still needs $n$ more queries to show the
fact. ∎

The next lemma gives a lower bound that justifies the linear dependency on
$\eta_{A}$ in our algorithmic results. In fact, it prohibits improvements over
the linear dependency unless the error grows quite large. But even then, we
complement the result with a different lower bound that grows stronger with
increasing number of errors.

######  Lemma 2.5.

For every $\eta_{A}\geq 1$, there is no deterministic algorithm that uses less
than

$\begin{cases}n-r+\eta_{A}&\text{if }1\leq\eta_{A}\leq\frac{n-r_{d}}{2}\\\
1+\lceil\log_{2}{n-r_{d}\choose\eta_{A}}\rceil&\text{if
}\eta_{A}\geq\frac{n-r_{d}}{2}\end{cases}$

clean queries in the worst-case, even if it knows $\eta_{A}$ upfront.

We prove the lemma by dividing the two different lower bounds into two lemmas,
Lemma 2.6 and Lemma 2.7, which we prove individually.

######  Lemma 2.6.

For every number of addition errors $\eta_{A}$ with
$1\leq\eta_{A}\leq\frac{n-r_{d}}{2}$, there is no deterministic algorithm that
uses less than $n-r+\eta_{A}$ clean queries in the worst-case even if the
algorithm knows the value of $\eta_{A}$ upfront and $\eta_{R}=0$.

###### Proof.

For the statement of the lemma, we assume that the algorithm has full
knowledge of $\eta_{A}$. However, we still require that the queries of the
algorithm can be used as a certificate for a third party _without_ knowledge
of $\eta_{A}$ to find a provable clean basis. Nevertheless, the assumption
that the algorithm knows $\eta_{A}$ still restricts the query answers that can
be returned by an adversary.

Fix $\eta_{A}\in\\{1,\ldots,\lfloor\frac{n-r_{d}}{2}\rfloor\\}$. Consider a
problem instance with the ground set of elements $E=\\{e_{1},\ldots,e_{n}\\}$.
Let $\mathcal{M}_{d}$ be a partition matroid with two classes of elements
$C_{1}=\\{e_{1},\ldots,e_{r_{d}}\\}$ and
$C_{2}=\\{e_{r_{d}+1},\ldots,e_{n}\\}$. Each set $S\subseteq E$ with $|E\cap
C_{1}|\leq r_{d}$ and $|E\cap C_{2}|=0$ is independent in $\mathcal{M}_{d}$.
Thus, $C_{1}$ is the only basis.

Consider an arbitrary algorithm for the instance. Depending on the algorithms
oracle calls, the adversary will create a clean partition matroid
$\mathcal{M}=(E,\mathcal{I})$ with the three classes of elements
$C_{1}=\\{e_{1},\ldots,e_{r_{d}}\\}$, $C_{2}$ and $C_{3}$. The elements of
$N:=\\{e_{r_{d}+1},\ldots,e_{n}\\}$ will be distributed to $C_{2}$ and $C_{3}$
depending on the algorithm’s actions, and the class capacities will be $r_{d}$
for $C_{1}$, $0$ for $C_{2}$ and $\eta_{A}$ for $C_{3}$. The adversary will
assign exactly $\eta_{A}$ elements to $C_{3}$, so the only basis of the clean
matroid will be $C_{1}\cup C_{3}$ and the addition error will be indeed
$\eta_{A}$.

The adversary starts out with empty $C_{2}$ and $C_{3}$ and later on adds
elements to these sets in a consistent manner. We distinguish between two
types of oracle calls by the algorithm: (i) queries to sets $S\subseteq E$
with $|(S\cap N)\setminus C_{3}|\geq 2$ and (ii) queries to sets $S\subseteq
E$ with $|(S\cap N)\setminus C_{3}|=1$ for the current $C_{3}$, which is
initially empty. All other oracle calls only contain elements of $(E\setminus
N)\cup C_{3}$. For such queries the adversary has to return true.

For queries of type (ii), the queried set $S\subseteq E$ contains a single
element $e\in(S\cap N)\setminus C_{3}$ for the current $C_{3}$. If $e$ has
already been fixed as a member of $C_{2}$, the oracle call returns false.
Otherwise, the adversary returns true and adds the single element of $(S\cap
N)\setminus C_{3}$ to $C_{3}$. After $\eta_{A}$ elements of $N$ have been
fixed as members of $C_{3}$, the adversary starts to return false on all
type-(ii) and assigns the single element $e\in(S\cap N)\setminus C_{3}$ to
$C_{2}$ instead.

Before we move on to type-(i) queries, we give some intuition on the strategy
of the adversary for type-(ii) queries. The adversary is designed to reveal
the elements $C_{3}$ that lead to addition errors as fast as possible if the
algorithm executes type-(ii) queries. If the algorithm would only execute
type-(ii) queries, then after $\eta_{A}$ such queries the algorithm would have
identified $C_{3}$. Since the algorithm knows $\eta_{A}$, it then also knows
that none of the remaining elements of $N\setminus C_{3}$ can be added to the
basis $C_{1}\cup C_{3}$ and, thus, has also identified $C_{2}$. However, in
order to query a certificate that proves to a third party without knowledge of
$\eta_{A}$ that the elements of $C_{2}$ can indeed not be added, the algorithm
will still require $|C_{2}|$ additional queries. Therefore, revealing $C_{3}$
fast will lead to $|C_{2}|+|C_{3}|=n-r+\eta_{A}$ queries if the algorithm only
executes type-(ii) queries. If the adversary would instead reveal the elements
of $C_{2}$ first, then the algorithm that only executes type-(ii) queries
could use the knowledge of $\eta_{A}$ to conclude after $n-r$ queries that
$C_{1}\cup C_{3}$ must be an independent set, as otherwise the number of
errors would be too small. In contrast to the previous case, the algorithm can
prove this efficiently with a single query to $C_{1}\cup C_{3}$. Thus,
revealing $C_{2}$ first would allow the algorithm to save queries.

For queries of type (i), the adversary will use a different strategy. If the
adversary would also start by returning true for type-(i) queries, then every
element of $N\setminus C_{3}$ that is part of the query would have to be added
to $C_{3}$. Since there are at least two such elements by definition of
type-(i) queries, a single query would prove membership of $C_{3}$ for at
least two elements. This would allow to reduce the number of queries below
$n-r+\eta_{A}$.

Instead, we define the adversary to return false as long as this is possible.
To make this query result consistent with the clean matroid, the adversary has
to add one of the queried elements to $C_{2}$. If $S\cap C_{2}\not=\emptyset$
already holds for the queried set $S$ and the current set $C_{2}$, then the
adversary can return false without adding a further element to $C_{2}$.
Otherwise, we define the adversary to select two elements $e_{1},e_{2}$ of
$(S\cap N)\setminus(C_{3}\cup C_{2})$. These elements must exist by definition
of type-(i) queries and as we assume $S\cap C_{2}=\emptyset$. The adversary
will later on add one of $e_{1}$ and $e_{2}$ to $C_{2}$ depending on the
algorithms actions. Assume without loss of generality that $e_{1}$ is the
element that appears first (or at the same time as $e_{2}$) in another later
oracle call. Once $e_{1}$ appears in this second query, the adversary adds
$e_{1}$ to $C_{2}$. If $C_{2}$ already contains $n-r_{d}-\eta_{A}$ elements,
then the adversary has to add it to $C_{3}$ instead and answer the query
accordingly.

To show the lower bound, we consider two cases: (1) $n-r_{d}-\eta_{A}$
elements are added to $C_{2}$ before $\eta_{A}$ elements are added to $C_{3}$
and (2) $\eta_{A}$ elements are added to $C_{3}$ before $n-r_{d}-\eta_{A}$
elements are added to $C_{2}$. If we show that the algorithm in both cases
needs at least $n-r+\eta_{A}$ queries, the lemma follows.

Case 1. First, assume the algorithm queries in such a way that
$n-r_{d}-\eta_{A}$ elements are assigned to $C_{2}$ before $\eta_{A}$ elements
are assigned to $C_{3}$. Since this is the case, an element $e$ is only added
to $C_{2}$ if there was a type-(i) query for which the adversary selected
$\\{e,e^{\prime}\\}$ with $e\not=e^{\prime}$ to potentially add to $C_{2}$. By
definition of the adversary, each such element $e$ is afterwards added to
$C_{2}$ while appearing in a second query after the type-(i) query. Thus, $e$
must appear in at least two queries. Note that these two queries are distinct
for each $e\in C_{2}$ because the assignment of $e$ is fixed immediately once
$e$ appears in a second query after being selected by the adversary as part of
the pair $\\{e,e^{\prime}\\}$ in the type-(i) query. In particular, for
$e^{\prime}$ to also be added to $C_{2}$, it would need to be selected by the
adversary in another type-(i) query and appear in another query afterwards.
Since $|C_{2}|=n-r_{d}-\eta_{A}$, this leads to a total number of queries of
least $2\cdot(n-r_{d}-\eta_{A})$. As $\eta_{A}\leq\frac{n-r_{d}}{2}$, we have
$2\cdot(n-r_{d}-\eta_{A})\geq 2\cdot(n-r_{d})-(n-r_{d})=n-r_{d}=n-r+\eta_{A}$.
If there exist elements that are never selected by the adversary in response
to a type-(i) query, then the adversary must add those elements to $C_{3}$ as
$C_{2}$ is already full. Since the algorithm knows $\eta_{A}$, it potentially
knows that this is the case and can prove that these elements are in $C_{3}$
with a single additional query to $C_{1}\cup C_{3}$.

Case 2. Next, assume the algorithm queries in such a way that $\eta_{A}$
elements are added to $C_{3}$ before $n-r_{d}-\eta_{A}$ elements are added to
$C_{2}$. Then, the algorithm must have executed $\eta_{A}$ type-(ii) queries
to sets $S$ where the unique element of $(S\cap N)\setminus C_{3}$ was added
to $C_{3}$ afterwards.

Each element $e\in C_{2}$ must appear in a query to a set $S$ for which each
other member is either part of $C_{1}$ or $C_{3}$ (or eventually added to
$C_{3}$). As the algorithm knows $\eta_{A}$, it might be able to conclude that
none of the elements in $N\setminus C_{3}$ can be added to the independent set
$C_{1}\cup C_{3}$ _without_ actually querying them. However, the queries of
the algorithm must be a certificate for a third party without knowledge of
$\eta_{A}$. Thus, despite knowing that none of these elements can be added,
the algorithm still has to prove it using type-(ii) queries. This leads to a
total of at least $n-r_{d}-\eta_{A}+\eta_{A}=n-r+\eta_{A}$ queries. ∎

######  Lemma 2.7.

For every number of removal errors $\eta_{A}$ with $1\leq\eta_{A}$, there is
no deterministic algorithm that uses less than
$1+\lceil\log_{2}{n-r_{d}\choose\eta_{A}}\rceil$ queries in the worst-case,
even if the algorithm knows the value of $\eta_{A}$ upfront.

###### Proof.

The idea is similar to Lemma 2.9. Consider an instance with the dirty matroid
$\mathcal{M}_{d}=(E,\mathcal{I}_{d})$ for the ground set of elements
$\\{e_{1},\ldots,e_{n}\\}$. Let $\mathcal{M}_{d}$ be a partition matroid with
the two classes $C_{1}=\\{e_{1},\ldots,e_{r_{d}}\\}$ and
$C_{2}=\\{e_{r_{d}+1},\ldots,r_{n}\\}$. Each set $I$ with $|I\cap C_{1}|\leq
r_{d}$ and $|I\cap C_{2}|\leq 0$ is independent in $\mathcal{M}_{d}$. Thus,
$C_{1}$ is the only dirty basis.

Fix a number of addition errors $\eta_{A}\geq 1$. The adversary will create a
clean matroid $\mathcal{M}=(E,\mathcal{I})$ by selecting $\eta_{A}$ elements
from $C_{2}$ and add to $C_{1}$ instead. Formally, the clean matroid will be a
partition matroid with the two classes $C_{1}^{\prime}=C_{1}\cup A$ and
$C^{\prime}_{2}=C_{2}\setminus A$ for some set $A\subseteq C_{2}$ with
$|A|=\eta_{A}$. The capacities for the classes are $r_{d}+\eta_{A}$ and $0$,
respectively.

Firstly, the algorithm has to query $C_{1}$, otherwise it cannot know whether
there’s some element in $C_{1}$ that should be removed (it does not know
$\eta_{R}$). Then, the adversary has to identify the set $A$ (or equivalently
$C_{2}\setminus A$) in order to execute a final query to the clean basis
$C_{1}\cup A$. In order to do so, it has to use queries of the form $D_{1}\cup
D_{2}$ where $D_{1}\subseteq C_{1}$ and $D_{2}\subseteq C_{2}$. The adversary
has $|C_{2}|\choose\eta_{A}$ choices to decide $A$, and each of the queries by
the algorithm can rule out at most one half of these choices (the adversary
can always choose to answer “yes" or “no" depending on which preserves more
choices). Thus the algorithm needs at least
$\lceil\log_{2}{|C_{2}|\choose\eta_{A}}\rceil=\lceil\log_{2}{n-r_{d}\choose\eta_{A}}\rceil$
queries. Note that this bound is weaker than that in Lemma 2.6 when $\eta_{A}$
is small compared to $n-r_{d}$. ∎

We conclude the discussion on addition errors by showing that there exists an
improved algorithm in terms of the error dependency if $\eta_{R}=0$ and
$\eta_{A}$ is large enough. Hence, a distinction depending on $\eta_{A}$ in
the lower bound (as in Lemma 2.5) is indeed necessary.

######  Lemma 2.8.

For problem instances with $\eta_{R}=0$ and
$\eta_{A}\geq\frac{3}{4}(n-r_{d})+1$, there exists an algorithm that executes
strictly less than $n-r+\eta_{A}$ clean queries in the worst-case.

###### Proof.

Let $B$ be a basis of the given dirty matroid $\mathcal{M}_{d}$. Let
$N=\\{e_{1},\ldots,e_{n-r_{d}}\\}$ denote the elements of $E\setminus B$
indexed in an arbitrary order. Note that $|N|\geq 1$ as $\eta_{R}=0$ and
$\eta_{A}\geq 1$. Consider the following algorithm:

  1. 1.

If $|N|\geq 2$, continue with Step 2. Otherwise, query
$B\cup\\{e\\}\in\mathcal{I}$ for the single element $e\in N$. Add $e$ to $B$
if this query returns true. Afterwards, terminate.

  2. 2.

Pick two arbitrary distinct elements $e,e^{\prime}$ of $N$ and execute the
oracle call $B\cup\\{e,e^{\prime}\\}\in\mathcal{I}$. Remove both elements from
$N$.

  3. 3.

If the oracle call returns true, then add $\\{e,e^{\prime}\\}$ to $B$.

  4. 4.

Otherwise, query $B\cup\\{e\\}\in\mathcal{I}$. If this returns true, add $e$
to $B$. Otherwise, query $B\cup\\{e^{\prime}\\}\in\mathcal{I}$. If this
returns true, add $e^{\prime}$ to $B$.

  5. 5.

If $N$ is empty now, then terminate. Otherwise, go to Step 1.

We show that this algorithm satisfies the asserted statement.

Assume for now that $|N|$ is even and, thus, no queries are executed in Step
1. We call one execution of Steps 1 to 5 an iteration. Let $k_{i}$ with
$i\in\\{0,1,2\\}$ denote the number of iterations in which $i$ many elements
have been added to $B$. Then, the number of queries executed by the algorithm
is at most $3\cdot(k_{0}+k_{1})+k_{2}$.

Since $(n-r_{d})-\eta_{A}$ elements of $N$ are not part of the basis $B$
computed by the algorithm, we must have $2\cdot
k_{0}+k_{1}=(n-r_{d})-\eta_{A}$ as $k_{0}$ iterations identify two such
elements each and $k_{1}$ iterations identify one such element each.
Similarly, we have $k_{1}+2\cdot k_{2}=\eta_{A}$. By combining the two
equalities, we obtain $k_{0}+k_{1}+k_{2}=\frac{n-r_{d}}{2}$. Hence, the number
of queries executed by the algorithm is at most

$\displaystyle 3\cdot(k_{0}+k_{1})+k_{2}$
$\displaystyle=\frac{n-r_{d}}{2}+2k_{0}+2k_{1}\leq\frac{n-r_{d}}{2}+2(2k_{0}+k_{1})=\frac{n-r_{d}}{2}+2(n-r_{d}-\eta_{A})$
$\displaystyle\leq\frac{n-r_{d}}{2}+2\left(\frac{n-r_{d}}{4}-1\right)=n-r_{d}-2=n-r+\eta_{A}-2.$

The last inequality uses our assumed lower bound on $\eta_{A}$.

We note that there is a straightforward example which shows that this analysis
is tight, where in particular $k_{0}=0$ and the algorithm alternatingly adds
two and one elements.

Finally, if $|N|$ is odd, we have one additional query in Step 1 of the
algorithm. Thus, the number of queries is in this case at most
$n-r+\eta_{A}-1$. ∎

Finally, we justify the logarithmic error-dependency on the removal error
$\eta_{R}$ in our algorithmic results for small $\eta_{R}$.

######  Lemma 2.9.

For every $\eta_{R}\geq 1$, there is no deterministic algorithm that uses less
than $n-r+1+\lceil\log_{2}{r_{d}\choose\eta_{R}}\rceil$ clean queries in the
worst-case even if the algorithm knows the value of $\eta_{R}$ upfront.
Further, if $\eta_{R}\leq\frac{r_{d}}{2^{k}}$ for some fixed $k\geq 0$, the
bound is at least $n-r+1+\lceil\eta_{R}(\log_{2}r_{d}-k)\rceil$.

###### Proof.

Consider an instance with the dirty matroid
$\mathcal{M}_{d}=(E,\mathcal{I}_{d})$ for the ground set of elements
$\\{e_{1},\ldots,e_{n}\\}$. Let $\mathcal{M}_{d}$ be a partition matroid with
the two classes $C_{1}=\\{e_{1},\ldots,e_{r_{d}}\\}$ and
$C_{2}=\\{e_{r_{d}+1},\ldots,e_{n}\\}$. Each set $I$ with $|I\cap C_{1}|\leq
r_{d}$ and $|I\cap C_{2}|\leq 0$ is independent in $\mathcal{M}_{d}$. Thus,
$C_{1}$ is the only dirty basis.

Fix a number of removal errors $\eta_{R}\geq 1$. The adversary will create a
clean matroid $\mathcal{M}=(E,\mathcal{I})$ by selecting $\eta_{R}$ elements
to remove from $C_{1}$ and add to $C_{2}$ instead. Formally, the clean matroid
will be a partition matroid with the two classes
$C_{1}^{\prime}=C_{1}\setminus R$ and $C^{\prime}_{2}=C_{2}\cup R$ for some
set $R\subseteq C_{1}$ with $|R|=\eta_{R}$. The capacities for the classes are
$r_{d}-\eta_{R}$ and $0$, respectively.

Consider an arbitrary deterministic algorithm. For each $e\in
C_{2}=C_{2}^{\prime}\setminus R$, the algorithm has to query a set $S$ with
$S\cap C_{2}=\\{e\\}$ and $S\setminus\\{e\\}\subseteq C_{1}^{\prime}$, as this
is the only way of verifying that the elements in $C_{2}$ cannot be added to
the basis. Even if the algorithm knows that $\eta_{A}=0$, it still has to
prove this by using such queries. This leads to at least $n-r_{d}\geq n-r+1$
queries.

For the elements in $R$, the algorithm has to do the same. However, it does
not know which elements of $C_{1}$ belong to $R$ and which do not. Instead,
the algorithm has to iteratively query subsets of $C_{1}$ until it has
sufficient information to identify the set $R$. Note that queries to sets
containing members of $C_{1}$ _and_ $C_{2}$ always return false independent of
whether the queried members of $C_{1}$ belong to $R$ or not, which means that
such queries do not reveal any information helpful for identifying $R$.

We can represent each such algorithm for identifying $R$ as a search tree. A
vertex $v$ in the search tree represents the current state of the algorithm
and is labeled by the set $P_{v}\subseteq C_{1}$ of elements that still could
potentially belong to $R$ given the information already obtained by the
algorithm and a family of subsets $\mathcal{S}_{v}$ such that each
$S\in\mathcal{S}_{v}$ is guaranteed to contain at least one member of $R$
given the algorithm’s information. For the root $r$ of the search tree, we
have $P_{r}=C_{1}$ and $\mathcal{S}_{r}=\\{C_{1}\\}$. As the algorithm
executes queries to sets $S\subseteq C_{1}$, it gains more information about
which elements could potentially belong to $R$. Thus, each vertex $v$ in the
search tree has (up-to) two successors $v^{\prime},v^{\prime\prime}$ with
different labels $P_{v^{\prime}}$ and $P_{v^{\prime\prime}}$ depending on the
answer to the query executed by the algorithm while being in the state
represented by $v$. The algorithm can only terminate once it reaches a state
$u$ in the search tree with $|P_{u}|=\eta_{R}$, because only then it has
identified the set $R=P_{u}$. We refer to such vertices as _leaves_. Since,
depending on the query results returned by the adversary, each subset of
$S\subseteq C_{1}$ with $|S|=\eta_{R}$ could be the set $R$, there are at
least ${|C_{1}|\choose\eta_{R}}={r_{d}\choose\eta_{R}}$ leaves.

The search tree representing the algorithm has a maximum out-degree of two and
at least ${r_{d}\choose\eta_{R}}$ leaves, which implies that the depth of the
search tree is at least $\lceil\log_{2}{r_{d}\choose\eta_{R}}\rceil$. Since
the adversary can select the query results in such a way that it forces the
algorithm to query according to a longest root-leaf-path, this implies that
the algorithm needs at least $\lceil\log_{2}{r_{d}\choose\eta_{R}}\rceil$
queries to identify $R$.

In total, the algorithm has to execute at least
$n-r+1+\lceil\log_{2}{r_{d}\choose\eta_{R}}\rceil$ queries. Note that
$\binom{n}{k}\geq\frac{n^{k}}{k^{k}}$ for any positive integer $n,k$ with
$k\leq n$. If $\eta_{R}$ is small compared to $r_{d}$, say,
$\eta_{R}\leq\frac{r_{d}}{2^{k}}$ for some constant $k\geq 0$, then
$\log_{2}{r_{d}\choose\eta_{R}}\geq\eta_{R}(\log_{2}{r_{d}}-k)$. ∎

##  3 Computing a Maximum-Weight Basis

We move to the weighted setting. Here, we assume that we are given a maximum-
weight basis $B_{d}\in\mathcal{B}_{d}^{*}$, which can be computed without any
clean oracle calls. The main difficulty compared to the unweighted setting can
be summarized as follows: In the unweighted setting, the error-dependent
algorithm first computes an _arbitrary_ maximal independent set
$B^{\prime}\subseteq B_{d}$ and then easily augments $B^{\prime}$ to a clean
basis. In the weighted setting however, there clearly can be independent sets
$B^{\prime}\subseteq B_{d}$ which are not part of any maximum-weight basis;
hence we need to be more careful. Finding such a special independent subset of
$B_{d}$ only by removing elements from $B_{d}$ and testing its independence
seems difficult: $B_{d}$ itself could be independent, but not part of any
maximum-weight basis. However, even in this case, $B_{d}$ can be very close to
a maximum-weight basis w.r.t. $\eta_{A}$ and $\eta_{R}$. Therefore, we cannot
avoid carefully modifying $B_{d}$ since strategies like the greedy algorithm
would use too many queries in this case.

Thus, we alternatingly add and remove elements to and from $B_{d}$.
Intuitively, we want to ensure, as the greedy algorithm, that we do not miss
to add elements with large weight. Thus, we try to add them as soon as
possible. However, even if they are part of every basis in $\mathcal{B}^{*}$,
this might result in a _dependent_ current solution unless we now remove
elements, which were not detectable before. An example of such a situation is
given in Figure 3. This observation rules out simple two-stage algorithms as
used in the unweighted case.

[t]0.45 $e_{1}$$e_{2}$$e_{3}$$e_{4}$$e_{5}$$e_{6}$$e_{7}$$e_{8}$$e_{9}$1\.
remove2\. add [t]0.45
$e_{1}$$e_{2}$$e_{3}$$e_{4}$$e_{5}$$e_{6}$$e_{7}$$e_{8}$$e_{9}$2\. add1\.
remove4\. add3\. remove

Figure 1: Modification to an arbitrary clean basis. Figure 2: Modification to
a maximum-weight clean basis. Adding $e_{2}$ is necessary for its high weight.
Element $e_{5}$ is only blocking after adding $e_{2}$ to $B_{d}-e_{9}$, hence
cannot be detected earlier. Figure 3: A matroid with elements
$e_{1},\ldots,e_{9}$ (displayed as circles) ordered left-to-right by non-
increasing weight. The elements of the maximum-weight dirty basis $B_{d}$ are
filled.

We now present our algorithm. Its full description is shown in Algorithm 2.
Given elements $E=\\{e_{1},\ldots,e_{n}\\}$ in non-decreasing order of their
weight, it maintains a preliminary solution which initially is set to the
dirty basis $B_{d}$. It modifies this solution over $n$ iterations and tracks
modifications in the variable sets $A\subseteq E\setminus B_{d}$ (_added_
elements) and $R\subseteq B_{d}$ (_removed_ elements). In every iteration
$\ell$, the algorithm selects elements to add and remove such that _at the
end_ of iteration $\ell$ its preliminary solution $(B_{d}\setminus R)\cup A$
satisfies two properties, which we define and motivate now.

Property $(i)$ requires that the preliminary solution $(B_{d}\setminus R)\cup
A$ up to $e_{\ell}$ should be a _maximal_ subset of some maximum-weight basis.
For the sake of convenience, we introduce the matroid
$\mathcal{M}^{*}=(E,\mathcal{I}^{*})$, where $\mathcal{I}^{*}$ is the set of
all subsets of $\mathcal{B}^{*}$. Then, we can use the following definition.

######  Definition 3.1.

We say that a set $S$ is _$k$ -safe_ if $S_{\leq k}\in\mathcal{I}^{*}$ and for
every $e\in E_{\leq k}\setminus S_{\leq k}$ it holds that $S_{\leq
k}+e\notin\mathcal{I}^{*}$.

In other words, a set $S$ is $k$-safe if it is a basis of the truncated
matroid of the $k$th prefix of $E$. Using this definition, Property $(i)$
requires that at the end of iteration $\ell$, the current solution
$(B_{d}\setminus R)\cup A$ is $\ell$-safe. Establishing this property in every
iteration will give us that the final solution is $n$-safe, and, thus, a
maximum-weight basis of $\mathcal{M}$. This works because the algorithm does
not modify its solution for the $\ell$th prefix of $E$ after the $\ell$th
iteration.

Algorithm 2 Find a Maximum-Weight Basis

0: dirty basis $B_{d}\subseteq E$, matroid $\mathcal{M}=(E,\mathcal{I})$

1: $A\leftarrow\emptyset;R\leftarrow\emptyset$ {_added_ / _removed_ elements}

2: while $(B_{d}\setminus R)\cup A\notin\mathcal{I}$ do

3: Find the _smallest_ index $i$ s.t. $((B_{d}\setminus R)\cup A)_{\leq
i}\notin\mathcal{I}$ via _binary search_.

4: $R\leftarrow R+e_{i}$

5: end while

6: for $\ell=1$ to $n$ do

7: if $e_{\ell}\notin B_{d}$ and $((B_{d}\setminus R)\cup
A+e_{\ell})_{\leq\ell}\in\mathcal{I}$ then

8: $A\leftarrow A+e_{\ell}$

9: if $(B_{d}\setminus R)\cup A\notin\mathcal{I}$ then

10: Find the _smallest_ index $i$ s.t. $((B_{d}\setminus R)\cup A)_{\leq
i}\notin\mathcal{I}$ via _binary search_.

11: $R\leftarrow R+e_{i}$

12: end if

13: end if

14: end for

15: return $(B_{d}\setminus R)\cup A$

To establish Property $(i)$ after every iteration without using too many clean
queries, it also maintains Property $(ii)$, which requires that at the end of
every iteration the current solution is independent, that is, $(B_{d}\setminus
R)\cup A\in\mathcal{I}$.

We now give some intuition on how our algorithm achieves this. Initially, say
for $\ell=0$, Property $(i)$ is fulfilled trivially. For the second property,
the algorithm greedily adds minimum-weight elements of $B_{d}$ to $R$ which
close a circuit in the smallest prefix of $(B_{d}\setminus R)\cup A$ (Lines
2-5). This subroutine can be implemented via binary search, as for the error-
dependent algorithm in Section 2.2. To guarantee both properties at the end of
iteration $\ell$, first observe that Property $(ii)$ holds as long as $A$ and
$R$ have not changed in this iteration. However, this might be necessary to
establish Property $(i)$. Intuitively, our algorithm wants to act like the
classic greedy algorithm to ensure $\ell$-safeness. Thus, it checks whether
$e_{\ell}$ should be in the solution by considering its solution for
$E_{\leq\ell}$. Clearly, if $e_{\ell}\in B_{d}\setminus R$, there is nothing
to modify (Line 7), because the current solution is independent due to
Property $(ii)$ for the previous iteration. Similarly, if $e_{\ell}\notin
B_{d}$ and the current solution for $E_{\leq\ell}$ together with $e_{\ell}$ is
independent, we add $e_{\ell}$ to our solution (Lines 7-8). However, by adding
an element, Property $(ii)$ can become false due to an introduced circuit,
which we have to break (Lines 9-12). Finally, there might be the situation
that $e_{\ell}\in B_{d}$ has been added to $R$ in an earlier iteration, so
$e_{\ell}\in R$. In this case, we clearly do not want to even consider adding
$e_{\ell}$ again, as queries for verifying this addition cannot be bounded by
our error measure. Indeed, removing and re-adding an element cannot be part of
any minimal modification distance. Thus, our algorithm skips such elements
(Line 7). To justify this, we prove that removing element $e_{\ell}$ is always
necessary, in the sense that there always is a circuit which $e_{\ell}$ breaks
and which cannot be broken by removing elements in _later_ iterations by Lines
9-12. This follows from classic matroid properties for circuits.

We now formally prove these properties.

######  Lemma 3.2 (Property (ii)).

At the beginning (end) of every iteration of Line 6, it holds that
$(B_{d}\setminus R)\cup A\in\mathcal{I}$.

###### Proof.

At the beginning of the first iteration, $(B_{d}\setminus R)\cup
A\in\mathcal{I}$ by the condition in Line 2. It suffices to show if
$(B_{d}\setminus R)\cup A\in\mathcal{I}$ holds before iteration $\ell=j$, then
it also holds before iteration $\ell=j+1$. If in iteration $\ell=j$, the
condition in Line 7 is not satisfied, then $A,R$ do not change and we are
done. The remaining case is that $e_{j}$ is added to $A$. If then
$(B_{d}\setminus R)\cup A\in\mathcal{I}$, Line 9 evaluates false and we are
done. Otherwise, that is, $(B_{d}\setminus R)\cup A\notin\mathcal{I}$, we
execute the binary search in Line 10 and add an element to $R$. To conclude
also this case, we argue that at the end of this iteration we have that
$(B_{d}\setminus R)\cup A\in\mathcal{I}$. Adding $e_{j}$ to our solution,
which by induction hypothesis was independent before, creates at most one (in
this case exactly one) circuit in our solution (cf. (39.35) in [33]). Since
the binary search in Line 10 detects exactly this unique circuit, an element
of the circuit is added to $R$, which breaks the circuit and makes
$(B_{d}\setminus R)\cup A$ independent again. ∎

######  Lemma 3.3 (Property (i)).

At the end of every iteration $\ell$ of Line 6, it holds that $(B_{d}\setminus
R)\cup A$ is $\ell$-safe.

###### Proof.

First, we introduce some notations. Let $A_{k},R_{k}$ be the sets represented
by the variables $A,R$ at the end of iteration $k$ (equivalently at the
beginning of iteration $k+1$). We prove by induction over the iterations of
Line 6 that the statement holds at the end of every iteration. First, note
that every set is $0$-safe, thus, this also applies to our solution before the
first iteration of Line 6. Let $\ell\in\\{1,\ldots,n\\}$. We write
$B=(B_{d}\setminus R_{\ell-1})\cup A_{\ell-1}$ for our preliminary solution
after iteration $\ell-1$, and $B^{\prime}=(B_{d}\setminus R_{\ell})\cup
A_{\ell}$ for the solution after iteration $\ell$. By induction hypothesis, we
can assume that $B$ is $(\ell-1)$-safe, and we now prove that $B^{\prime}$ is
$\ell$-safe. To this end, we distinguish three cases concerning element
$e_{\ell}$.

In the first case we assume that $e_{\ell}\notin B_{d}$, Then, the algorithm
makes one more query (Line 7). If $B_{\leq\ell}+e_{\ell}\notin\mathcal{I}$, it
must hold that $B$ is $\ell$-safe, and since in this case $B=B^{\prime}$, we
are done. Otherwise, that is, $B_{\leq\ell}+e_{\ell}\in\mathcal{I}$, we add
$e_{\ell}$ to $A$ and, thus, $B_{\leq\ell}+e_{\ell}=B^{\prime}_{\leq\ell}$. We
now prove that $B^{\prime}_{\leq\ell}$ is part of a maximum-weight basis,
which implies that $B^{\prime}$ is $\ell$-safe. Let $B^{*}$ be some optimal
basis such that $B_{\leq\ell-1}\subseteq B^{*}$. Such a basis exists because
$B$ is $(\ell-1)$-safe by assumption. If $e_{\ell}\in B^{*}$, then also
$B^{\prime}_{\leq\ell}\subseteq B^{*}$, and we are done. Otherwise, that is,
$e_{\ell}\notin B^{*}$, there must be a circuit $C$ in $B^{*}+e_{\ell}$.
Moreover, $C$ must contain some other element $e_{k}$ with $k>\ell$, because
$B^{\prime}_{\leq\ell}\in\mathcal{I}$ due to Lemma 3.2. By the ordering of the
elements, $w_{e_{\ell}}\geq w_{e_{k}}$, and therefore $B^{*}+e_{\ell}-e_{k}$
is a maximum-weight basis. Further, it contains $B^{\prime}_{\leq\ell}$. Thus,
we conclude $B^{\prime}_{\leq\ell}\in\mathcal{I}^{*}$.

For the second case, suppose that $e_{\ell}\in B_{d}\setminus R_{\ell-1}$.
Thus, the condition in Line 7 evaluates false, and we have $B=B^{\prime}$.
Thus, $B^{\prime}_{\leq\ell}=B_{\leq\ell-1}+e_{\ell}$, and we can prove
analogously to the previous case that $B^{\prime}_{\leq\ell}$ in included in a
maximum-weight basis.

Finally, it remains the case where $e_{\ell}\in R_{\ell-1}$. In this case,
$e_{\ell}$ is added to $R$ in some earlier iteration $\ell^{\prime}<\ell$,
and, thus, $e_{\ell}\notin B^{\prime}$. Also, $B=B^{\prime}$ because
$e_{\ell}\in B_{d}$. We show that $B^{\prime}_{\leq\ell-1}+e_{\ell}$ is
dependent, which implies that $B^{\prime}$ is $\ell$-safe. To this end, we
prove for $q=\ell^{\prime},\ldots,\ell-1$ the invariant that $((B_{d}\setminus
R_{q})\cup A_{q})_{\leq\ell-1}+e_{\ell}$ contains a circuit $C$ such that
$e_{\ell}\in C$ and that $e_{\ell}$ is the element with the largest index in
$C$. Note that the invariant holds at the time $e_{\ell}$ is added to $R$ in
iteration $\ell^{\prime}$ due to Lines 3 and 10. Suppose the invariant holds
for $q=j-1$, witnessed by circuit $C_{1}$. We now prove the invariant for
$q=j$. If $C_{1}\subseteq((B_{d}\setminus R_{j})\cup
A_{j})_{\leq\ell-1}+e_{\ell}$, we are done. Otherwise, the algorithm must have
added element $e_{j}\in C_{1}$ to $R$ in iteration $j$. By Lines 3 and 10,
$e_{j}$ is the element with largest index in a circuit $C_{2}$ in
$(B_{d}\setminus R_{j-1})\cup A_{j}$. As $e_{\ell}$ has the largest index in
$C_{1}$ by induction hypothesis and $e_{j}\in C_{1}$, we conclude $j<\ell$.
Thus, $e_{\ell}\notin C_{2}$. Since $e_{j}\in C_{1}\cap C_{2}$ and
$e_{\ell}\in C_{1}\setminus C_{2}$, there exists a circuit
$C_{3}\subseteq(C_{1}\cup C_{2})\setminus\\{e_{j}\\}$ such that $e_{\ell}\in
C_{3}$ (cf. Theorem 39.7 in [33]). In particular,
$C_{3}\subseteq((B_{d}\setminus R_{j})\cup A_{j})_{\leq\ell-1}+e_{\ell}$ and
$e_{\ell}$ has the largest index in $C_{3}$. This makes $C_{3}$ a witness for
the invariant for $q=j$, and, thus, concludes the proof. ∎

Since there can be at most $n$ elements in $R$, the algorithm clearly
terminates, and we have an immediate corollary.

######  Corollary 3.4.

Algorithm 2 terminates with an $n$-safe set.

It remains to bound the number of clean queries. Let $A$ and $R$ be fixed to
their final sets. We assume that elements are non-increasingly ordered by
their weight; among elements of _equal weight_ , elements of $B_{d}$ come
_before_ elements of $E\setminus B_{d}$. Given such an ordering, the algorithm
does modify $B_{d}$ to a closest basis of $\mathcal{B}^{*}$ w.r.t. to our
error measure.

######  Lemma 3.5.

It holds that $\lvert A\rvert\leq\eta_{A}$ and $\lvert R\rvert\leq\eta_{R}$.

###### Proof.

Let $A^{*}=A(B_{d})$, $R^{*}=R(B_{d})$ be some minimum modification sets for
$B_{d}$ and $I^{*}=(B_{d}\cup A^{*})\setminus R^{*}$. We choose $A^{*}$ and
$R^{*}$ such that $|R\bigtriangleup R^{*}|+|A\bigtriangleup A^{*}|$ is
minimized. By definition, $I^{*}\in\mathcal{B}^{*}$, and, by 1.2,
$|R^{*}|\leq\eta_{R}$ and $|A^{*}|\leq\eta_{A}$.

Let $I$ denote the solution computed by the algorithm. If all elements have
distinct weights, it is well known that a maximum-weight basis is unique.
Since $I$ is $n$-safe by Corollary 3.4, no elements can be added to $I$ while
maintaining independence in $\mathcal{M}^{*}$. Hence, $I=I^{*}$. Further,
since $R\cap A=\emptyset$, we have $\lvert R\rvert=\lvert R^{*}\rvert$ and
$\lvert A\rvert=\lvert A^{*}\rvert$, which asserts the statement in this case.
The same argumentation holds if some elements have the same weight and
$I=I^{*}$ holds.

Hence, we assume from now on $I\neq I^{*}$ for the sake of contradiction. Let
$\kappa<n$ be the number of distinct weights. We partition $E$ according to
weight into _weight classes_ of elements with the same weight. We use
subscript $i$ on any set of elements to refer to the subset of elements of the
$i$th weight class. Since $I$ is $n$-safe by Corollary 3.4, both $I$ and
$I^{*}$ have maximum weight. Using again the observation that $A\cap
R=\emptyset$, we have that

$\lvert R_{i}\rvert-\lvert A_{i}\rvert=\lvert R^{*}_{i}\rvert-\lvert
A_{i}^{*}\rvert\text{ and }\lvert I_{i}\rvert=\lvert I^{*}_{i}\rvert$ (1)

for every $i\in[\kappa]$.

We now either find new modification sets $\bm{\tilde{}}{R}^{*}$ and
$\bm{\tilde{}}{A}^{*}$ with
$|R\bigtriangleup\bm{\tilde{}}{R}^{*}|+|A\bigtriangleup\bm{\tilde{}}{A}^{*}|<|R\bigtriangleup
R^{*}|+|A\bigtriangleup A^{*}|$ or show $I^{*}\notin\mathcal{B}^{*}$; a
contradiction in both cases. In the former case, we additionally require that

$\lvert R^{*}\rvert=\lvert\bm{\tilde{}}{R}^{*}\rvert,\;\lvert
A^{*}\rvert=\lvert\bm{\tilde{}}{A}^{*}\rvert\text{ and
}\bm{\tilde{}}{I}^{*}\in\mathcal{B}^{*}.$ (2)

That is, $\bm{\tilde{}}{R}^{*}$ and $\bm{\tilde{}}{A}^{*}$ are minimum
modification sets.

Let $i$ be the weight class of the largest weight such that $I_{i}\neq
I^{*}_{i}$. Since $\lvert I_{i}\rvert=\lvert I^{*}_{i}\rvert$, we have
$I^{*}_{i}\setminus I_{i}\neq\emptyset$.

If there exists an element $e\in(I_{i}^{*}\setminus I_{i})\cap A^{*}_{i}$,
there exists an element $e^{\prime}\in I_{i}\setminus I^{*}_{i}$ with
$\bm{\tilde{}}{I}^{*}:=I^{*}-e+e^{\prime}\in\mathcal{B}^{*}$ due to the basis
exchange property (cf. Theorem 39.6 in [33]). If
$e^{\prime}\in((B_{d})_{i}\setminus R_{i})\setminus I^{*}_{i}$, setting
$\bm{\tilde{}}{R}^{*}:=R^{*}-e^{\prime}$ and $\bm{\tilde{}}{A}^{*}:=A^{*}-e$
we obtain
$\bm{\tilde{}}{I}^{*}:=(B_{d}\setminus\bm{\tilde{}}{R}^{*})\cup\bm{\tilde{}}{A}^{*}\in\mathcal{B}^{*}$.
However, this contradicts our assumption that $A^{*}$ and $R^{*}$ are minimum
modification sets for $B_{d}$ since
$\lvert\bm{\tilde{}}{R}^{*}\rvert+\lvert\bm{\tilde{}}{A}^{*}\rvert<\lvert
R^{*}\rvert+\lvert A^{*}\rvert$. Thus, $e^{\prime}\in A_{i}\setminus
I^{*}_{i}$. Therefore, setting $\bm{\tilde{}}{R}^{*}:=R^{*}$ and
$\bm{\tilde{}}{A}^{*}:=A^{*}-e+e^{\prime}$ implies (2) and contradicts our
minimality assumption on $|R\bigtriangleup R^{*}|+|A\bigtriangleup A^{*}|$
since $e^{\prime}\in A\setminus A^{*}$.

Otherwise, it must hold that $A^{*}_{i}\subseteq A_{i}$, and there must exist
an element $e\in(I_{i}^{*}\setminus I_{i})\cap((B_{d})_{i}\setminus
R^{*}_{i})$. If $A_{i}^{*}=A_{i}$, there must exist an element
$e^{\prime}\in((B_{d})_{i}\setminus R_{i})\cap R^{*}_{i}$ such that
$I^{*}-e+e^{\prime}\in\mathcal{B}^{*}$ by the basis exchange property. Setting
$\bm{\tilde{}}{R}_{i}^{*}=R_{i}^{*}-e^{\prime}+e$ and
$\bm{\tilde{}}{A}^{*}=A^{*}$ in this case implies (2) and contradicts again
our minimality assumption on $|R\bigtriangleup R^{*}|+|A\bigtriangleup
A^{*}|$. Therefore, $A_{i}^{*}\subsetneq A_{i}$ and, in particular, $\lvert
A_{i}^{*}\rvert<\lvert A_{i}\rvert$. Due to (1) and (2), $\lvert
R_{i}^{*}\rvert<\lvert R_{i}\rvert$. Observe that for all $1\leq j\leq i-1$,
we have by our choice of $i$ that $I^{*}_{j}=I_{j}$. In the prefix
$P=\bigcup_{j=1}^{i-1}I_{j}\cup(B_{d})_{i}$, our algorithm guarantees that the
largest independent set in $P$ has size $\lvert P\rvert-\lvert R_{i}\rvert$.
This implies $P\setminus R^{*}_{i}\notin\mathcal{I}$, which contradicts our
assumption that $I^{*}$ is a basis. ∎

We finally introduce a charging scheme and apply the above lemma to derive an
error-dependent bound for Algorithm 2.

######  Lemma 3.6.

Algorithm 2 computes a maximum-weight basis with at most
$n-r+1+2\eta_{A}+\eta_{R}\cdot\lceil\log_{2}(r_{d})\rceil$ clean queries.

###### Proof.

The correctness follows from Corollary 3.4. It remains to bound the number of
clean queries. Note that we use clean oracle calls only in Lines 2,3,7,9 and
10.

In Lines 3 and 10, each removal incurs a binary search, which costs at most
$\lceil\log_{2}(r_{d})\rceil$ queries. Since every binary search increments
the size of $R$, the total number of queries used in these lines is at most
$\lceil\log_{2}(r_{d})\rceil\cdot|R|$. In Line 2, the number of queries is
equal to the number of elements added to $R$ in Line 4 plus a final one where
the condition evaluates false, which we charge extra. Similarly, we charge the
queries in Line 9 to the removals in Line 10 and again charge the final query
in Line 9, which evaluates false, to the added element in Line 8. In Line 7,
we have that each $e\in E\setminus B_{d}$ incurs a query, hence the total
number is $n-r_{d}$.

Summarized, the total number of clean queries is at most
$\lceil\log_{2}(r_{d})\rceil\cdot|R|+|R|+1+|A|+n-r_{d}.$ Using
$r=r_{d}+\eta_{A}-\eta_{R}$ and Lemma 3.5, we conclude the proof. ∎

Complementing this algorithmic result, we give the following lower bound. It
proves that our error-dependent guarantees for the unweighted case are not
possible anymore in the weighted case. Hence, it separates both settings.

######  Lemma 3.7.

Every deterministic algorithm for finding a maximum-weight basis executes
strictly more than $n-r+\eta_{A}+\eta_{R}\cdot\lceil\log_{2}(r_{d})\rceil+1$
clean oracle calls in the worst-case.

###### Proof.

Consider the ground set of elements $E=\\{e_{1},\ldots,e_{n}\\}$ with weights
$w_{e_{i}}=n+1-i$ for all $e_{i}\in E$. Let the dirty matroid
$\mathcal{M}_{d}$ be a partition matroid that is defined by the two classes
$C_{1}=\\{e_{1},\ldots,e_{n-1}\\}$ and $C_{2}=\\{e_{n}\\}$ with capacities
$n-2$ and $1$, respectively. That is, each set $I\subseteq E$ with $|I\cap
C_{1}|\leq n-2$ and $|I\cap C_{2}|\leq 1$ is independent in $\mathcal{M}_{d}$.
Then, $B_{d}=E\setminus\\{e_{n-1}\\}$ is the only dirty maximum-weight basis.
Furthermore, if $\mathcal{M}=\mathcal{M}_{d}$, then the only way of verifying
that $B_{d}$ is indeed a maximum-weight clean basis is to query $B_{d}$ and
$\\{e_{1},\ldots,e_{n-1}\\}$. The first query is necessary to prove
independence and the second query is necessary to prove that $B_{d}$ is a
maximum-weight basis. Note that querying $B_{d}$ and $E$ would also suffice to
prove that $B_{d}$ is a basis, but it would not exclude the possibility that
$\\{e_{1},\ldots,e_{n-1}\\}$ is also a basis with strictly more weight. Thus,
the queries $B_{d}$ and $E$ are not a certificate for proving that $B_{d}$ is
a maximum-weight basis.

Consider an arbitrary deterministic algorithm. We prove the statement by
giving an adversary that, depending on the algorithms clean oracle calls,
creates a clean matroid $\mathcal{M}$ that forces the algorithm to execute
strictly more clean oracle calls than the bound of the lemma.

First, we can observe that if $\mathcal{M}=\mathcal{M}_{d}$, we have
$n-r+\eta_{A}+\lceil\log_{2}(r_{d})\rceil\cdot\eta_{R}+1=2$. This means that
if the algorithm starts by querying anything but $B_{d}$ or
$P:=\\{e_{1},\ldots,e_{n-1}\\}$, the adversary can just use $\mathcal{M}_{d}$
as the clean matroid. By the argumentation above, the algorithm then has to
also query $B_{d}$ and $P$, leading to $3>2$ queries. Thus, it only remains to
consider algorithms that start by querying either $B_{d}$ or $P$.

Case 1: The algorithm queries $P$ first. In this case, the adversary will
return false. Note that this answer is consistent with the dirty matroid
$\mathcal{M}_{d}$. This implies that the algorithm has to query $B_{d}$ next,
as the adversary can otherwise select $\mathcal{M}=\mathcal{M}_{d}$, which
again forces the algorithm to also query $B_{d}$. Thus, the algorithm would
execute $3>2$ queries.

Consider the case where the second query of the algorithm goes to $B_{d}$. We
define the adversary to return that $B_{d}$ is not independent.

Instead the adversary will select a clean partition matroid that is defined by
the three classes
$C_{1}^{\prime}=\\{e_{1},\ldots,e_{n-2}\\}\setminus\\{\bar{e}\\}$ for an
element $\bar{e}\in\\{e_{1},\ldots,e_{n-2}\\}$ that is selected by the
adversary in response to the further clean oracle calls by the algorithm,
$C_{2}^{\prime}=\\{\bar{e},e_{n-1}\\}$ and $C_{3}^{\prime}=\\{e_{n}\\}$. The
capacities will be $n-3$, $0$ and $1$, respectively. This implies $\eta_{R}=1$
as the element $\bar{e}$ induces a removal error, and $\eta_{A}=0$ as
$e_{n-1}$ is still not part of any maximum-weight basis, and $n-r=2$. The
bound of the lemma then becomes
$n-r+\eta_{A}+\lceil\log_{2}(r_{d})\rceil\cdot\eta_{R}+1=3+\lceil\log_{2}(r_{d})\rceil$.

Following the proof of Lemma 2.9, the adversary can force the algorithm to use
$\lceil\log_{2}\binom{r_{d}-1}{1}\rceil=\lceil\log_{2}{(r_{d}-1)}\rceil$
oracle calls to find the element $\bar{e}$. If we pick $r_{d}$ as a
sufficiently large power of two, we get
$\lceil\log_{2}{(r_{d}-1)}\rceil=\lceil\log_{2}{r_{d}}\rceil$.

Note that queries containing $e_{n-1}$ do not contribute to finding $\bar{e}$
as they always return false. This implies that the algorithm needs an
additional query containing $e_{n-1}$ to prove that
$(B_{d}\setminus\\{\bar{e}\\})\cup\\{e_{n-1}\\}$ is not independent in the
clean matroid. Combined with the two queries to $B_{d}$ and $P$ and the
$\lceil\log_{2}{r_{d}}\rceil$ queries for finding $\bar{e}$, this already
leads to $3+\lceil\log_{2}(r_{d})\rceil$ queries. Any additional query would
imply that the algorithm executes strictly more queries than the bound of the
lemma.

The algorithm however needs one additional query to verify that
$B_{d}\setminus\\{\bar{e}\\}$ is independent. Note that the query
$B_{d}\setminus\\{\bar{e}\\}$ could in principle be executed during the search
for $\bar{e}$. However, the adversary would only answer true to a query of
form $B_{d}\setminus\\{e\\}$ for any $e\in B_{d}$ if $e$ is the only remaining
choice for $\bar{e}$ since returning true to that query would reveal
$e=\bar{e}$, which the adversary never does. However, if $e$ is the only
remaining choice for $\bar{e}$, then algorithm already knows $\bar{e}$, which
means that the query is not counted within the
$\lceil\log_{2}{r_{d}-1}\rceil=\lceil\log_{2}{r_{d}}\rceil$ for finding
$\bar{e}$. In total, this leads to
$4+\lceil\log_{2}{r_{d}}\rceil>3+\lceil\log_{2}{r_{d}}\rceil$ queries.

Case 2: The algorithm queries $B_{d}$ first. Then, the adversary will return
true, which is consistent with the dirty matroid. In order to avoid three
queries in case that the adversary chooses $\mathcal{M}=\mathcal{M}_{d}$, the
algorithm has to query $P$ next. The adversary will answer that $P$ is indeed
independent and choose $E$ as the only basis of the clean matroid. Afterwards,
the algorithm has to query also $E$ to prove that $E$ is indeed independent.
This leads to a total of three queries. However, we have $n-r=0$, $\eta_{A}=1$
and $\eta_{R}=0$, which implies
$n-r+\eta_{A}+\lceil\log_{2}(r_{d})\rceil\cdot\eta_{R}+1=2<3$. ∎

##### Application of the Robustification Framework

To complete the picture for the weighted case, we generalize the ideas used
for robustifying the error-dependent algorithm (cf. Section 2.3) and combine
it with the concepts developed above. The core idea for robustifying Algorithm
2 is to start a binary search only after a sufficient number of linear search
steps. However, as observed above (cf. Figure 3), we cannot remove all
blocking elements in one iteration. Although the simple argument that the
linear search partitions $B_{d}$ still holds, it does not cover the total
removal cost, because a later addition can create a removal at a position
which has already been checked. To circumvent this issue, we observe that in
Algorithm 2, we actually do not need to remove every element from the current
solution as soon as we can detect it; we just need to decide whether in
iteration $\ell$ element $e_{\ell}$ should be part of the solution.

In our robustified algorithm (Algorithm 3) we exploit this as follows. While
in Algorithm 2 we linearly check prefixes of $E\setminus B_{d}$ for additions,
we now linearly check prefixes of $E$ for additions (Lines 4-7) _and_ removals
(Lines 8-12). However, for the sake of a good error-dependency, we count these
removal checks (cf. increment counter $q$ in Line 9) and execute a binary
search only if we checked enough elements in $B_{d}$ linearly (Lines 15-18).
Then, we can again bound the total cost for the binary searches using a
density argument. Whenever we remove an element, we charge the previous cost
of the linear searches to this removal error and reset $q$, which re-activates
the linear search. However, if the current solution is already independent, we
do not want to search for removal errors at all (cf. Lines 2 and 9 in
Algorithm 2). Unfortunately, doing such a check after every addition and
removal already rules out a robustness close to $n$. Thus, we slightly delay
this check w.r.t. the counter $q$ (Line 13), and stop the removal search
accordingly (Line 14). Finally, whenever an element is added, we make sure
that the linear search is running or that we start it again (Line 6), as a new
circuit could have been introduced in our solution.

Algorithm 3 Find a Maximum-Weight Basis (robustified)

0: dirty basis $B_{d}$, matroid $(E,\mathcal{I})$, integer $k\geq 1$

1: $A\leftarrow\emptyset;R\leftarrow\emptyset$;
$d_{\max}\leftarrow\max_{e_{i}\in B_{d}}i\;$

2: $q\leftarrow 0;\text{LS}\leftarrow\mathrm{true}$ {linear search counter /
flag}

3: for $\ell=1$ to $n$ do

4: if $e_{\ell}\notin B_{d}$ then

5: if $((B_{d}\setminus R)\cup A+e_{\ell})_{\leq\ell}\in\mathcal{I}$ then

6: $A\leftarrow A+e_{\ell}$ and $\text{LS}\leftarrow\mathrm{true}$

7: end if

8: else if $e_{\ell}\in B_{d}\setminus R$ and $\text{LS}=\mathrm{true}$ then

9: $q\leftarrow q+1$

10: if $((B_{d}\setminus R)\cup A)_{\leq\ell}\notin\mathcal{I}$ then

11: $R\leftarrow R+e_{\ell}$ and $q\leftarrow 0$

12: end if

13: if $\ell=d_{\max}$ or ($q=k-1$ and $(B_{d}\setminus R)\cup
A\in\mathcal{I}$) then

14: $q\leftarrow 0$ and $\text{LS}\leftarrow\mathrm{false}$

15: else if $q=k\lceil\log_{2}r_{d}\rceil$ then

16: Find the _smallest_ index $i$ s.t. $((B_{d}\setminus R)\cup A)_{\leq
i}\notin\mathcal{I}$ via _binary search_.

17: $R\leftarrow R+e_{i}$ and $q\leftarrow 0$

18: end if

19: end if

20: end for

21: return $(B_{d}\setminus R)\cup A$

See 1.1

###### Proof.

To prove this theorem, we consider Algorithm 3. It is not hard to see that the
correctness of Algorithm 3 follows from the correctness of Algorithm 2. We now
prove the stated bound on the number of clean oracle calls.

The algorithm uses clean oracle calls only in Lines 5, 10, 13, and 16. We
separately prove the error-dependent bound an the robustness bound.

##### Proof of the error-dependent bound

We start by bounding the number of queries in Lines 5, 13, and 16:

  * •

In Line 5, each element $e\in E\setminus B_{d}$ incurs a query and the total
number of such queries is $n-r_{d}$.

  * •

In Line 16, the binary search is incurred by elements in $R$. Thus the total
number of such queries is at most $|R|\lceil\log_{2}r_{d}\rceil$.

  * •

To bound the number of queries in Line 13, we observe that whenever $q$
reaches $k-1$, we execute one such query, unless $\ell=d_{\max}$, because then
we know that $((B_{d}\setminus R)\cup A)_{\leq\ell}=(B_{d}\setminus R)\cup A$
and the independence follows because the condition in Line 10 evaluated false.
Therefore, it suffices to bound how often $q$ reaches $k-1$. Note that $q$ can
be decreased to $0$ only in Lines 11, 14, and 17. Lines 11 and 17 correspond
to an element in $R$ and Line 13 sets the variable LS to $\mathrm{false}$
which must have been set to $\mathrm{true}$ by Line 2 or Line 6 (in which case
we added an element to $A$). Hence, we conclude that the number of times $q$
reaches $k-1$, which upper bounds the number of queries executed in Line 13,
is at most $|R|+|A|+1$.

In total, the number of clean queries in Lines 5, 13, and 16 is at most

$n-r_{d}+|R|\lceil\log_{2}r_{d}\rceil+|R|+|A|+1.$ (3)

It remains to bound the number of queries executed in Line 10. To this end, we
first show $q\leq k-2$ when the algorithm terminates. This follows from the
fact that at the end of the algorithm we have a feasible solution by Corollary
3.4. Assume for contradiction that $q\geq k-1$ at the end of the algorithm.
Then at some previous iteration, we entered Line 13. Consider the iteration
with largest index in which we entered Line 13. Note that the if-statement in
Line 13 has to be false as otherwise $q$ was set to $0$ again. But, in
particular, this implies that the current solution $(B_{d}\setminus R)\cup A$
in this iteration is not independent and hence the algorithm must enter Line
11 or Line 16 at some later iteration in order to output an independent
solution. This implies that $q$ is set to $0$ again, a contradiction.

Observe that $q$ is increased by $1$ before each query executed in Line 10 and
the number of times $q$ is increased is at most the total decrease of $q$ plus
$k-2$ (the value of $q$ at the end of the algorithm). As shown before, $q$ can
only be decreased by $k-1$ in Line 14 which happens at most $|A|+1$ times, or
decreased by at most $k\lceil\log_{2}r_{d}\rceil$ in Lines 11 or 17, which
happens $|R|$ times. To be more precise, Line 14 is executed at most $|A|$
(rather than $|A|+1$) times if $q>0$ at the end of algorithm. This follows
from the fact that $q>0$ implies $\text{LS}=\mathrm{true}$ at the end of the
algorithm, which means Line 14 is not executed after the last execution of
Line 6.

To finally bound the number of queries in Line 10, we distinguish whether
$q=0$ or $q>0$ holds at the end of the algorithm. If $q>0$ at the end of the
algorithm, then the number of queries executed in Line 10 is at most
$|A|\cdot(k-1)+|R|\cdot k\lceil\log_{2}r_{d}\rceil+k-2$, where the additive
$k-2$ are caused by the final at most $k-2$ increases of $q$ at the end of the
algorithm after the last reset of $q$. If $q=0$, then there are no final
queries after the last reset of $q$. However, as argued above, Line 14 is
potentially executed $(|A|+1)$ times instead of only $|A|$ times. Thus, the
number of queries in Line 10 in that case is at most
$(|A|+1)\cdot(k-1)+|R|\cdot k\lceil\log_{2}r_{d}\rceil$. In both cases, the
number of queries in Line 10 is at most

$|A|\cdot(k-1)+|R|\cdot k\lceil\log_{2}r_{d}\rceil+k-1.$ (4)

We can conclude the target bound on the number of clean queries by summing up
Equation (3) and Equation (4), plugging in r${}_{d}+|A|-|R|=r$ and using Lemma
3.5, which also holds for Algorithm 3:

$\displaystyle
n-r_{d}+|R|\lceil\log_{2}r_{d}\rceil+|R|+|A|+1+|A|\cdot(k-1)+|R|\cdot
k\lceil\log_{2}r_{d}\rceil+k-1$ $\displaystyle=n-r_{d}+|R|+|A|\cdot
k+|R|\cdot(k+1)\lceil\log_{2}r_{d}\rceil+k$
$\displaystyle=n-(r-|A|+|R|)+|R|+|A|\cdot
k+|R|\cdot(k+1)\lceil\log_{2}r_{d}\rceil+k$
$\displaystyle=n-r_{d}+|A|\cdot(k+1)+|R|\cdot(k+1)\lceil\log_{2}r_{d}\rceil+k$
$\displaystyle\leq
n-r_{d}+\eta_{A}\cdot(k+1)+\eta_{R}\cdot(k+1)\lceil\log_{2}r_{d}\rceil+k.$

##### Proof of the robustness bound

Let $Q_{A}$ denote the set of queries of Line 5 that trigger the execution of
Line 6, i.e., $Q_{A}$ contains the queries that detect an addition error. Let
$Q_{N}$ denote the queries of Line 5 that do not trigger the execution of Line
6 and let $Q_{R}$ denote the set of all remaining queries.

First, observe that each query in $Q_{N}$ is incurred by a distinct element of
$E\setminus(B_{d}\cup A)$. Thus, we have $|Q_{N}|=n-r_{d}-|A|$.

Next, we continue by bounding $|Q_{A}|$ and $|Q_{R}|$. To this end, we
partition $Q_{R}$ into _segments_ $T_{i}$. A segment $T_{i}$ contains the
queries of $Q_{R}$ that occur after the $i$’th reset of variable $q$ but
before reset $i+1$. We use _reset_ to refer to an execution of Line 2, 11, 4
or 17 that sets the variable $q$ to $0$. Since we count the execution of Line
2 as a reset, segment $T_{1}$ contains the queries of $Q_{R}$ that take place
between the execution of Line 2 and the first execution of Line 11, 4 or 17
(if such an execution exists).

For a segment $T_{i}$, let $q_{i}$ denote the current value of variable $q$ at
the final query of the segment. We distinguish between _long_ , _short_ and
_tiny_ segments:

  * •

A segment $T_{i}$ is long if it contains queries executed in Line 16.

  * •

A segment $T_{i}$ is tiny if it satisfies $q_{i}\leq k-1$.

  * •

A segment is $T_{i}$ is short if it is neither long nor tiny.

First, consider the long segments. Let $I_{\text{long}}$ denote the index set
of the long segments and let $L_{\text{long}}=\sum_{i\in
I_{\text{long}}}q_{i}$. Each long segment $T_{i}$ contains
$k\lceil\log_{2}r_{d}\rceil$ queries of Line 10 since $q_{i}$ must increase to
at least this value in order to trigger queries in Line 16 and $q$ is reset
afterwards. Additionally, the segment must contain a query of Line 13 as
$q_{i}$ increases to a value larger than $k-1$. Finally, $T_{i}$ contains up-
to $\lceil\log_{2}r_{d}\rceil$ queries of Line 16. Thus, a long segment
$T_{i}$ contains at most $(k+1)\lceil\log_{2}r_{d}\rceil+1$ queries. The
number of long segments is at most
$\frac{L_{\text{long}}}{k\lceil\log_{2}r_{d}\rceil}$ as each long segment
$T_{i}$ has $q_{i}=k\lceil\log_{2}r_{d}\rceil$. By using that the total number
of long segments is also at most $|R|$ (since each execution of Line 16 finds
a distinct removal error), we get that the total number of queries over all
long segments is

$\sum_{i\in
I_{\text{long}}}|T_{i}|\leq\frac{L_{\text{long}}}{k\lceil\log_{2}r_{d}\rceil}((k+1)\lceil\log_{2}r_{d}\rceil+1)=\left(1+\frac{1}{k}\right)L_{\text{long}}+|I_{\text{long}}|\leq\left(1+\frac{1}{k}\right)L_{\text{long}}+|R_{\text{long}}|,$

where $R_{\text{long}}\subseteq R$ denotes the set of removal errors that
where added to $R$ in Line 17.

Next, consider the short segments. As before let $I_{\text{short}}$ denote the
index set of the short segments and let $L_{\text{short}}=\sum_{i\in
I_{\text{short}}}q_{i}$. A short segment $T_{i}$ contains exactly $q_{i}$
queries of Line 10. Furthermore, it must contain a query of Line 13 since it
is not tiny and, thus, has $q_{i}\geq k-1$. This implies that $T_{i}$ contains
$q_{i}+1=(1+\frac{1}{q_{i}})q_{i}$ queries. As $T_{i}$ is not tiny, we have
$(1+\frac{1}{q_{i}})q_{i}\leq(1+\frac{1}{k})q_{i}$. We can conclude that the
total number of queries over all short segments is at most

$\sum_{i\in I_{\text{short}}}|T_{i}|\leq\left(1+\frac{1}{k}\right)\sum_{i\in
I_{\text{short}}}q_{i}=\left(1+\frac{1}{k}\right)\cdot L_{\text{short}}.$

Finally, consider the tiny segments. As before let $I_{\text{tiny}}$ denote
the index set of the tiny segments and let $L_{\text{tiny}}=\sum_{i\in
I_{\text{tiny}}}q_{i}$. Observe that each tiny segment $T_{i}$ either ends
with the reset in Line 14 or it ends even before the reset because the
algorithm terminates before $q_{i}$ reached value $k-1$. The latter case can
happen at most once in the final segment. Since each reset in Line 14 sets the
LS flag to $\mathrm{false}$ and the flag is only set to $\mathrm{true}$ again
in Line 6 when an addition error is detected, the number of tiny segments is
at most $1+|A|$.

Each tiny segment contains at most $q_{i}+1$ queries (up-to $q_{i}$ in Line 10
and up-to one in Line 13). Let $t$ denote the index of the final segment and
let $\bm{\bar{}}{L}_{tiny}=\sum_{i\in I_{\text{tiny}}\setminus\\{t\\}}q_{i}$.
Without the final segment, we get

$\sum_{i\in I_{\text{tiny}}\setminus\\{t\\}}|T_{i}|=\sum_{i\in
I_{\text{tiny}}\setminus\\{t\\}}(q_{i}+1)=\bm{\bar{}}{L}_{\text{tiny}}+|I_{\text{tiny}}|-1=\bm{\bar{}}{L}_{\text{tiny}}+|A|.$

We can combine the bound for the queries of these tiny segments with a bound
for $|Q_{A}|$. Since each query of $Q_{A}$ detects an addition error in Line
6, we have $|Q_{A}|=|A|$. Furthermore, we have
$\bm{\bar{}}{L}_{\text{tiny}}+|A|=k\cdot|A|$ as there are $|A|$ tiny segments
that are not the final one and each such segment $T_{i}$ has $q_{i}=k-1$.
Putting it together we achieve the following combined bound:

$\sum_{i\in
I_{\text{tiny}}\setminus\\{t\\}}|T_{i}|+|Q_{A}|=\bm{\bar{}}{L}_{\text{tiny}}+|A|+|A|\leq\left(1+\frac{1}{k}\right)\cdot(\bm{\bar{}}{L}_{\text{tiny}}+|A|).$

It remains to consider the final segment $T_{t}$. If this segment does not
query in Line 13, then we have $|T_{t}|=q_{t}$. In this case, we can combine
all previous bounds and use that
$L_{\text{long}}+L_{\text{short}}+\bm{\bar{}}{L}_{\text{tiny}}+q_{t}+|A|\leq
r_{d}+|A|-|R_{\text{long}}|$ to conclude that the total number of queries is
at most:

$\displaystyle|Q_{N}|+|Q_{R}|+|Q_{A}|$ $\displaystyle=|Q_{N}|+\sum_{i\in
I_{\text{long}}}|T_{i}|+\sum_{i\in I_{\text{short}}}|T_{i}|+\sum_{i\in
I_{\text{tiny}}\setminus\\{t\\}}|T_{i}|+|Q_{A}|+|T_{t}|$ $\displaystyle\leq
n-r_{d}-|A|+\left(1+\frac{1}{k}\right)\cdot(\bm{\bar{}}{L}_{\text{tiny}}+|A|+L_{\text{short}}+L_{\text{long}})+|R_{\text{long}}|+q_{t}$
$\displaystyle\leq
n-r_{d}-|A|+\left(1+\frac{1}{k}\right)\cdot(r_{d}+|A|-|R_{\text{long}}|)+|R_{\text{long}}|$
$\displaystyle\leq\left(1+\frac{1}{k}\right)\left(n-r_{d}-|A|+r_{d}+|A|-|R_{\text{long}}|+|R_{\text{{long}}}|\right)=\left(1+\frac{1}{k}\right)n.$

Note that the last inequality holds because $|A|\leq n-r_{d}$.

If $T_{t}$ executes a query in Line 13, then we have $|T_{t}|=q_{t}+1$. On the
other hand, the query in Line 13 implies $\ell<d_{\max}$ for the current index
$\ell$ when the query is executed and for $d_{\max}=\max_{e_{i}\in B_{d}}i$.
This means that the variable $q$ is increased at most
$r_{d}-|R_{\text{long}}|-1$ times and, thus,
$L_{\text{long}}+L_{\text{short}}+\bm{\bar{}}{L}_{\text{tiny}}+q_{t}+|A|\leq
r_{d}+|A|-|R_{\text{long}}|-1$. Plugging these inequalities into the
calculations above yields the same result:

$\displaystyle|Q_{N}|+|Q_{R}|+|Q_{A}|$ $\displaystyle=|Q_{N}|+\sum_{i\in
I_{\text{long}}}|T_{i}|+\sum_{i\in I_{\text{short}}}|T_{i}|+\sum_{i\in
I_{\text{tiny}}\setminus\\{t\\}}|T_{i}|+|Q_{A}|+|T_{t}|$ $\displaystyle\leq
n-r_{d}-|A|+\left(1+\frac{1}{k}\right)\cdot(\bm{\bar{}}{L}_{\text{tiny}}+|A|+L_{\text{short}}+L_{\text{long}})+|R_{\text{long}}|+q_{t}+1$
$\displaystyle\leq
n-r_{d}-|A|+\left(1+\frac{1}{k}\right)\cdot(r_{d}+|A|-|R_{\text{long}}|-1)+|R_{\text{long}}|+1$
$\displaystyle\leq\left(1+\frac{1}{k}\right)\left(n-r_{d}-|A|+r_{d}+|A|-|R_{\text{long}}|-1+|R_{\text{{long}}}|+1\right)=\left(1+\frac{1}{k}\right)n.$

This concludes the proof of Theorem 1.1. ∎

##  4 Extensions and Future Work

In this section we briefly discuss potential extensions of our model and some
open problems for future work. Further details and proofs are deferred to
Appendix A.

###  4.1 Rank Oracles

Another common type of matroid oracles is the rank oracle: Given any
$S\subseteq E$, a rank oracle returns the cardinality of a maximum independent
set contained in $S$, denoted by $r(S)$. Since $r(S)=|S|$ if and only if
$S\in\mathcal{I}$, our previous algorithmic results for independence oracles
immediately transfer. Moreover, for the unweighted setting, we can even reduce
the number of oracle calls using a rank oracle, also implying that some of the
lower bounds from Section 2.4 do not hold. For example, given $B_{d}$ we can
compute its rank $r(B_{d})$ and obtain $\eta_{R}=|B_{d}|-r(B_{d})$ and decide
whether to remove elements via binary search or immediately switch to the
greedy algorithm. Further, we can improve the dependency on $\eta_{A}$ if
$\eta_{A}$ is small as we can find the elements to be added via a binary
search. Hence, we get the following result.

######  Proposition 4.1.

There is an algorithm that computes a clean basis with at most the minimum of

$\min\\{\eta_{A}\cdot\lceil\log_{2}(n-r_{d})\rceil,n-r_{d}\\}+2+\eta_{R}\cdot\lceil\log_{2}r_{d}\rceil$

and $n+1$ many clean rank-oracle calls.

For future work it would be interesting to see if the error-dependency and the
worst-case bound can be improved, and if rank oracles can be used to improve
the results for the weighted setting.

###  4.2 Dirty Independence Oracle with Cost

In this section, we consider the generalized setting where a dirty oracle call
has cost 1 and a clean oracle call has cost $p>1$, and our objective is to
minimize the total cost. Using the same requirements on algorithms as before,
Lemma 2.4 still holds, giving a lower bound $p(n-r+1)$. Note that the previous
results assume that $p\gg 1$ in this setup.

The main takeaway of this generalization is that it can be beneficial for an
algorithm to delay dirty oracle calls for clean oracle calls, depending on $p$
and $r$. This contrasts the previous sections, where we can meet lower bounds
by computing a dirty basis upfront.

To see this, we consider two algorithms and assume for simplicity that
$\mathcal{M}_{d}=\mathcal{M}$. The first algorithm starts with $E$ and removes
elements via binary search until it reaches an independent set. It only uses
clean oracle calls of total cost $p(n-r)\lceil\log_{2}(n)\rceil+p$. The second
algorithm computes a dirty basis and verifies it, incurring a total cost of
$n+p(n-r+1)$, as $\mathcal{M}_{d}=\mathcal{M}$. Thus, for small $p$ and large
$r$, the first algorithm incurs less cost than the second algorithm, which is
optimal among the class of algorithms which only initially use dirty oracle
calls. In particular, having access to rank oracles, one can compute the value
of $r$ upfront using one clean oracle call and, thus, select the better
algorithm.

###  4.3 Matroid Intersection

In the _matroid intersection problem_ we are given two matroids
$\mathcal{M}^{1}=(E,\mathcal{I}^{1})$ and
$\mathcal{M}^{2}=(E,\mathcal{I}^{2})$ on the same set of elements $E$ and we
seek a maximum set of elements $X\subseteq E$ that is independent in both
matroids, i.e., $X\in\mathcal{I}^{1}\cap\mathcal{I}^{2}$.

The textbook algorithm for finding such a maximum independent set is to
iteratively increase the size of a solution one by one using an augmenting-
path type algorithm until no further improvement is possible. This algorithm
has a running time of $O(r^{2}n)$ [15]. There are faster algorithms known for
matroid intersection, which run in time $O(nr^{3/4})$ [5] and in time
$O(n^{1+o(1)})$ for the special case of two partition matroids [10]. (In a
_partition matroid_ $\mathcal{M}=(E,\mathcal{I})$, the elements are
partitioned into _classes_ $C_{i}$ with capacities $k_{i}$, and a set
$S\subseteq E$ is independent if and only if $|C_{i}\cap S|\leq k_{i}$ holds
for each $C_{i}$.) Here, we focus on improving the running time of the simple
textbook algorithm by (i) using dirty oracles calls in each of the
augmentation steps and (ii) by computing a warm-start solution using an
optimal dirty solution, i.e., a feasible solution of a certain size dependent
on the error.

##### Matroid Intersection via Augmenting Paths

Our error measure is as follows: We define
$\eta_{1}=\\{F\in\mathcal{I}_{d}^{1}\mid F\notin\mathcal{I}^{1}\\}$ and
$\eta_{2}=\\{F\in\mathcal{I}_{d}^{2}\mid F\notin\mathcal{I}^{2}\\}$ to be the
number of different sets which are independent in the dirty matroid but not
independent in the clean matroid. In order to simplify the setting, we assume
here that (i) the dirty matroids are supersets of the clean matroids, i.e.,
$\mathcal{I}^{1}\subseteq\mathcal{I}^{1}_{d}$ and
$\mathcal{I}^{2}\subseteq\mathcal{I}^{2}_{d}$, and (ii) that the clean
matroids are partition matroids. We note that in general the intersection of
two partition matroids can be reduced to finding a maximum $b$-matching.

######  Proposition 4.2.

There is an algorithm that computes an optimum solution for matroid
intersection using at most
$(r+1)\cdot(2+(\eta_{1}+\eta_{2})\cdot(\lceil\log_{2}(n)\rceil+2))$ clean
oracle calls.

##### Matroid Intersection via Warm-Starting

We show how to exploit the dirty matroids to obtain a good starting solution
that is independent in both clean matroids. The idea of warm-starting using
predictions has been used for other prediction models in [14, 9, 31] for
problems like weighted bipartite matching or weighted matroid intersection.
These results are tailored to the weighted setting and do not directly
translate to improvements in the unweighted case. As error measure we adjust
the removal error for matroid intersection: Let
$s_{d}^{*}=\max_{S_{d}\in\mathcal{I}^{1}_{d}\cap\mathcal{I}^{2}_{d}}|S_{d}|$
and define
$\mathcal{S}_{d}^{*}=\\{S_{d}\in\mathcal{I}^{1}_{d}\cap\mathcal{I}^{2}_{d}\mid|S_{d}|=s_{d}^{*}\\}$
to be the set of optimum solutions to the dirty matroid intersection problem.
We define
$\eta_{r}=\max_{S_{d}\in\mathcal{S}_{d}^{*}}\min_{S_{c}\in\mathcal{I}^{1}\cap\mathcal{I}^{2}}\\{|S_{d}\setminus
S_{c}|:S_{c}\subseteq S_{d}\\}$.

Our algorithm starts by computing an optimum solution to the dirty matroid and
then greedily removes elements until we obtain a feasible solution for the
clean matroid. By using the observation that this reverse greedy algorithm is
a $2$-approximation in the number of to be removed elements, i.e., $\eta_{r}$,
we obtain the following result.

######  Proposition 4.3.

There is an algorithm that computes a feasible solution
$S_{c}^{\prime}\in\mathcal{I}^{1}\cap\mathcal{I}^{2}$ of size
$|S_{c}^{\prime}|\geq s_{d}^{*}-2\eta_{r}$ using at most
$2+2\eta_{r}\cdot(1+\lceil\log_{2}(n)\rceil)$ clean oracle calls.

## Acknowledgements

We thank Kevin Schewior for initial discussions on the topic of this paper.

## References

  * [1] Xingjian Bai and Christian Coester.  Sorting with predictions.  In NeurIPS, 2023.
  * [2] Evripidis Bampis, Bruno Escoffier, Michael Lampis, and Vangelis Th. Paschos.  Multistage matchings.  In SWAT, volume 101 of LIPIcs, pages 7:1–7:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.
  * [3] Evripidis Bampis, Bruno Escoffier, Kevin Schewior, and Alexandre Teiller.  Online multistage subset maximization problems.  Algorithmica, 83(8):2374–2399, 2021.
  * [4] MohammadHossein Bateni, Prathamesh Dharangutte, Rajesh Jayaram, and Chen Wang.  Metric clustering and MST with strong and weak distance oracles.  CoRR, abs/2310.15863, 2023.
  * [5] Joakim Blikstad.  Breaking O(nr) for matroid intersection.  In ICALP, volume 198 of LIPIcs, pages 31:1–31:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
  * [6] Niv Buchbinder, Shahar Chen, and Joseph Naor.  Competitive analysis via regularization.  In SODA, pages 436–444. SIAM, 2014.
  * [7] Niv Buchbinder, Shahar Chen, Joseph Naor, and Ohad Shamir.  Unified algorithms for online learning and competitive analysis.  Math. Oper. Res., 41(2):612–625, 2016.
  * [8] Deeparnab Chakrabarty, Yin Tat Lee, Aaron Sidford, Sahil Singla, and Sam Chiu-wai Wong.  Faster matroid intersection.  In FOCS, pages 1146–1168. IEEE Computer Society, 2019.
  * [9] Justin Y. Chen, Sandeep Silwal, Ali Vakilian, and Fred Zhang.  Faster fundamental graph algorithms via learned predictions.  In ICML, volume 162 of Proceedings of Machine Learning Research, pages 3583–3602. PMLR, 2022.
  * [10] Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva.  Maximum flow and minimum-cost flow in almost-linear time.  In FOCS, pages 612–623. IEEE, 2022.
  * [11] Markus Chimani, Niklas Troost, and Tilo Wiedera.  Approximating multistage matching problems.  Algorithmica, 84(8):2135–2153, 2022.
  * [12] Markus Chimani, Niklas Troost, and Tilo Wiedera.  A general approximation for multistage subgraph problems.  In LAGOS, volume 223 of Procedia Computer Science, pages 334–342. Elsevier, 2023.
  * [13] Edith Cohen, Graham Cormode, Nick G. Duffield, and Carsten Lund.  On the tradeoff between stability and fit.  ACM Trans. Algorithms, 13(1):7:1–7:24, 2016.
  * [14] Michael Dinitz, Sungjin Im, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii.  Faster matchings via learned duals.  Advances in neural information processing systems, 34:10393–10406, 2021.
  * [15] Jack Edmonds.  Submodular functions, matroids, and certain polyhedra, combinatorial structures and their applications, r. guy, h. hanani, n. sauer, and j. schonheim, eds.  New York, pages 69–87, 1970.
  * [16] Jack Edmonds.  Matroids and the greedy algorithm.  Math. Program., 1(1):127–136, 1971.
  * [17] David Eisenstat, Claire Mathieu, and Nicolas Schabanel.  Facility location in evolving metrics.  In ICALP (2), volume 8573 of Lecture Notes in Computer Science, pages 459–470. Springer, 2014.
  * [18] Thomas Erlebach, Murilo S. de Lima, Nicole Megow, and Jens Schlöter.  Sorting and hypergraph orientation under uncertainty with predictions.  In IJCAI, pages 5577–5585. ijcai.org, 2023.
  * [19] Thomas Erlebach, Murilo Santos de Lima, Nicole Megow, and Jens Schlöter.  Learning-augmented query policies for minimum spanning tree with uncertainty.  In ESA, volume 244 of LIPIcs, pages 49:1–49:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.
  * [20] Till Fluschnik, Rolf Niedermeier, Carsten Schubert, and Philipp Zschoche.  Multistage s-t path: Confronting similarity with dissimilarity in temporal graphs.  In ISAAC, volume 181 of LIPIcs, pages 43:1–43:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
  * [21] Dimitris Fotakis, Loukas Kavouras, and Lydia Zakynthinou.  Online facility location in evolving metrics.  Algorithms, 14(3):73, 2021.
  * [22] Anupam Gupta, Kunal Talwar, and Udi Wieder.  Changing bases: Multistage optimization for matroids and matchings.  In ICALP, volume 8572 of Lecture Notes in Computer Science, pages 563–575. Springer, 2014.
  * [23] Avinatan Hassidim and Yaron Singer.  Submodular optimization under noise.  In COLT, volume 65 of Proceedings of Machine Learning Research, pages 1069–1122. PMLR, 2017.
  * [24] Elad Hazan and Satyen Kale.  Online submodular minimization.  J. Mach. Learn. Res., 13:2903–2922, 2012.
  * [25] Lingxiao Huang, Yuyi Wang, Chunxue Yang, and Huanjian Zhou.  Efficient submodular optimization under noise: Local search is robust.  In NeurIPS, 2022.
  * [26] Shinji Ito.  Submodular function minimization with noisy evaluation oracle.  In NeurIPS, pages 12080–12090, 2019.
  * [27] Sam John, Akshay Gadde, and Balu Adsumilli.  Rate distortion optimization over large scale video corpus with machine learning.  In ICIP, pages 1286–1290. IEEE, 2020.
  * [28] Matt J. Kusner, Yu Sun, Nicholas I. Kolkin, and Kilian Q. Weinberger.  From word embeddings to document distances.  In ICML, volume 37 of JMLR Workshop and Conference Proceedings, pages 957–966. JMLR.org, 2015.
  * [29] Alexander Lindermayr and Nicole Megow.  Repository of papers on algorithms with predictions, 2024.  http://algorithms-with-predictions.github.io/ [Accessed: (January 31, 2024)].
  * [30] Michael Mitzenmacher and Sergei Vassilvitskii.  Algorithms with predictions.  Commun. ACM, 65(7):33–35, 2022.
  * [31] Shinsaku Sakaue and Taihei Oki.  Discrete-convex-analysis-based framework for warm-starting algorithms with predictions.  In NeurIPS, 2022.
  * [32] Baruch Schieber, Hadas Shachnai, Gal Tamir, and Tami Tamir.  A theory and algorithms for combinatorial reoptimization.  Algorithmica, 80(2):576–607, 2018.
  * [33] Alexander Schrijver.  Combinatorial Optimization - Polyhedra and Efficiency.  Algorithms and Combinatorics. Springer, 2003.
  * [34] Sandeep Silwal, Sara Ahmadian, Andrew Nystrom, Andrew McCallum, Deepak Ramachandran, and Seyed Mehran Kazemi.  Kwikbucks: Correlation clustering with cheap-weak and expensive-strong signals.  In ICLR. OpenReview.net, 2023.
  * [35] Yaron Singer and Avinatan Hassidim.  Optimization for approximate submodularity.  In NeurIPS, pages 394–405, 2018.
  * [36] Tatsuya Terao.  Faster matroid partition algorithms.  In ICALP, volume 261 of LIPIcs, pages 104:1–104:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.
  * [37] Taraneh Younesian, Dick H. J. Epema, and Lydia Y. Chen.  Active learning for noisy data streams using weak and strong labelers.  CoRR, abs/2010.14149, 2020.
  * [38] Chicheng Zhang and Kamalika Chaudhuri.  Active learning from weak and strong labelers.  In NIPS, pages 703–711, 2015.

##  Appendix A Proofs Omitted from Section 4

###  A.1 Discussion Omitted from Section 4.1

Another commonly used type of matroid oracle is the rank oracle: given any
$S\subseteq E$, a rank oracle returns the cardinality of a maximum independent
set contained in $S$, denoted by $r(S)$. We show in this section that a rank
oracle can be much more powerful than an independence oracle for our problem.
First note that since $r(S)=|S|$ if and only if $S\in\mathcal{I}$, our
previous results for independence oracles immediately translate. Moreover, we
can even reduce the number of oracle calls using a rank oracle. We briefly
discuss key ideas for the unweighted case below. It would be interesting to
see whether these ideas can also be used for the weighted case.

We start by adapting the simple algorithm from Section 2.1: Assume w.l.o.g.
$B_{d}\neq\emptyset$. If $r(B_{d})\neq|B_{d}|$ ($B_{d}\notin\mathcal{I}$), we
run the greedy algorithm. Otherwise, we check whether $r(E)=|B_{d}|$. If it
holds, we can conclude $B_{d}\in\mathcal{B}$ and are done. (This is the main
difference compared to the simple algorithm with an independence oracle.) If
not, we greedily try to add each element $e\in E\setminus B_{d}$ using in
total $n-|B_{d}|\leq n-1$ queries. Thus, in every case the algorithm does at
most $n+1$ clean oracle calls. Moreover, unlike the simple algorithm with an
independence oracle, it only does 2 oracle calls if $B_{d}\in\mathcal{B}$. In
particular, this shows that Lemma 2.4 does not hold for rank oracles anymore.

Using the same idea, we can improve the number of oracle calls whenever
$B_{d}\in\mathcal{B}$ for the error-dependent algorithm from Section 2.2 to
$2$. Furthermore, we can also improve its worst-case number of queries from
$\Theta(n\log_{2}n)$ to $n+1$. Recall that this bad case happens when
$\eta_{R}$ is large. However, now we can simply compute $r(B_{d})$ and obtain
$\eta_{R}=|B_{d}|-r(B_{d})$. Depending on $\eta_{R}$, we then decide whether
to remove elements via binary-search or immediately switch to the greedy
algorithm. In particular, achieving this worst-case guarantee of $n+1$ _does
not_ affect the error-dependent bound on the number of oracle calls.

Finally, we can improve the dependency on $\eta_{A}$. Recall that in the
error-dependent algorithm, we iteratively augment an independent set $B$ with
$\eta_{A}$ many elements from $E\setminus B_{d}$ to a basis. But with a rank
oracle, we can find these elements faster via binary search: find the first
prefix $(E\setminus B_{d})_{\leq i}$ which satisfies $r(B\cup(E\setminus
B_{d})_{\leq i})>r(B)$, and add $(E\setminus B_{d})_{=i}$ to $B$. Doing this
exhaustively incurs at most $\eta_{A}\lceil\log_{2}(n-r_{d})\rceil$ clean
oracle calls. Thus, whenever
$\eta_{A}<\frac{n-r_{d}}{\lceil\log_{2}{(n-r_{d})}\rceil}$, this strategy
gives an improved error-dependent bound over considering elements in
$E\setminus B_{d}$ linearly. Furthermore, this condition can be easily checked
with the rank oracle. Note that this contrasts Lemma 2.5.

To conclude the discussion, we obtain the following proposition. See 4.1

###  A.2 Proofs Omitted from Section 4.3

In the matroid intersection problem we are given two matroids
$\mathcal{M}^{1}=(E,\mathcal{I}^{1})$ and
$\mathcal{M}^{2}=(E,\mathcal{I}^{2})$ on the same set of elements $E$ and we
seek to find a maximum set of element $X\subseteq E$ such that
$X\in\mathcal{I}^{1}\cap\mathcal{I}^{2}$, i.e., it is independent in both
matroids. For $i\in\\{1,2\\}$ we define $r_{i}$ to be the rank of matroid
$\mathcal{I}^{i}$.

####  A.2.1 Matroid Intersection via Augmenting Paths

The textbook algorithm for finding such a maximum independent set is to
iteratively increase the size of a solution by one and eventually reach a
point in which no improvement is possible; in that case we also get a
certificate: $U\subseteq E$ with $\lvert X\rvert\geq r_{1}(U)+r_{2}(E\setminus
U)$. Given some feasible solution $X\in\mathcal{I}^{1}\cap\mathcal{I}^{2}$, in
every iteration the algorithm executes the following steps.

  1. 1.

Construct the directed bipartite exchange graph $D(X)$ for sets $X$ and
$E\setminus X$, where for every $x\in X$ and $y\in E\setminus X$ there is an
edge $(x,y)$ if $X-x+y\in\mathcal{I}^{1}$ and there is an edge $(y,x)$ if
$X-x+y\in\mathcal{I}^{2}$. Compute sets $Y_{1}=\\{y\in E\setminus X\mid
X+y\in\mathcal{I}^{1}\\}$ and $Y_{2}=\\{y\in E\setminus X\mid
X+y\in\mathcal{I}^{2}\\}$.

  2. 2.

If $Y_{1}=\emptyset$ terminate with certificate $U=E$. If $Y_{2}=\emptyset$
terminate with certificate $U=\emptyset$. Otherwise, compute a shortest path
$P$ between any vertex of $Y_{1}$ and any vertex of $Y_{2}$.

  3. 3.

If no such path exists, terminate with the certificate $U\subseteq E$ of
elements for which there exists a directed path in $D(X)$ to some element of
$Y_{2}$. Otherwise, augment $X$ along $P$, that is, $X\leftarrow X\triangle
P$, and continue with the next iteration.

We call the path found in step 2 an _augmenting path_. The running time of
this classic algorithm is $O(r^{2}n)$ [15], where $n=|E|$ and
$r=\min\\{r_{1},r_{2}\\}$. Recently, there has been a lot of significant
progress concerning the running times for matroid intersection, culminating in
the currently best running time of $O(nr^{3/4})$ for general matroids [5] and
time $O(n^{1+o(1)})$ for special cases, e.g., the intersection of two
partition matroids [10].

Here, we focus on improving the running-time of the simple textbook algorithm
for matroid intersection, by (i) using dirty oracles calls in each of the
augmentation steps or (ii) by using warm-starting ideas, i.e., by computing a
feasible solution of a certain size dependent on the error using an optimal
dirty solution.

Formally, additionally to the input for matroid intersection we are also given
two dirty matroids $\mathcal{M}^{1}_{d}=(E,\mathcal{I}^{1}_{d})$ and
$\mathcal{M}^{2}_{d}=(E,\mathcal{I}^{2}_{d})$. Our goal is to improve the
classic textbook algorithm from above by using dirty oracle calls. We attempt
the following approach: Given a feasible solution $X$ (for the clean oracles),
we do one iteration of the above algorithm using the dirty oracles. If there
is an augmenting path, which is also an augmenting path for the clean
matroids, we augment our solution and go to the next iteration. Otherwise, we
found an augmenting path using dirty oracles, which is not an augmenting path
for the clean matroids. In this case we do a binary search to find the error,
update our dirty matroids and start the algorithm again. Finally, if there is
no augmenting path in the dirty matroid, we need to augment the solution using
clean oracle calls, as we do not benefit from using the dirty oracle anymore.
To avoid this situation, throughout this section we assume that the dirty
matroids are supersets of the clean matroids, i.e.,
$\mathcal{I}^{1}\subseteq\mathcal{I}^{1}_{d}$ and
$\mathcal{I}^{2}\subseteq\mathcal{I}^{2}_{d}$.

Further, in step 2 of the augmenting path algorithm it is crucial that the
path from $Y_{1}$ to $Y_{2}$ is a path without chords111A chord $e$ of some
$s$-$t$ path $P$ is an edge such that $P+e$ admits an $s$-$t$ path
$P^{\prime}$ that is strictly shorter than $P$., as otherwise the computed
solution may not be feasible. Note that in step 2 we compute a shortest path,
which is always a path without chords. Therefore, if we use the dirty oracles
to compute a shortest path w.r.t. the dirty oracles, we need to verify in each
step that the computed path has no chords for the clean matroids as well. To
avoid such a situation, we restrict to the case that the clean matroids are
partition matroids, as for those matroids we do not need to find an augmenting
path without chords, but just _any_ augmenting path. We note that in general
the intersection of two partition matroids can be reduced to finding a maximum
$b$-matching.

Therefore, from now on we assume that the clean matroids are partition
matroids and that the dirty matroids are supersets of the clean matroids. Our
algorithm works as follows. We assume that we are given a feasible solution
for the clean matroid and wish to increase its size by one if possible.
Additionally, we are given two lists $\mathcal{F}_{1}$ and $\mathcal{F}_{2}$
of false dirty queries for $\mathcal{M}^{1}_{d}$ and $\mathcal{M}^{2}_{d}$,
respectively, i.e., two list of sets $F\subseteq E$ for which we have already
queried that $F$ is not independent in $\mathcal{M}^{1}$ or $\mathcal{M}^{2}$,
respectively (but it was independent in the respective dirty matroid). For
each iteration, we use the following algorithm.

Algorithm 4 Augmenting Path via Dirty Oracles

1: Input: A feasible solution $X\in\mathcal{I}^{1}\cap\mathcal{I}^{2}$ and two
lists of false dirty queries $\mathcal{F}_{1},\mathcal{F}_{2}$.

2: Output: A feasible solution
$X^{\prime}\in\mathcal{I}^{1}\cap\mathcal{I}^{2}$ and list of false dirty
queries $\mathcal{F}^{\prime}_{1},\mathcal{F}_{2}^{\prime}$ or $X$ if it is
maximum.

3: Compute augmenting path $P$ in $D_{d}^{\mathcal{F}}(X)$

4: if there is no such path $P$ then

5: return $X$ (in this case $X$ is optimal).

6: end if

7: if $P$ is augmenting path for clean matroids then

8: $X^{\prime}\leftarrow X\Delta P$,
$\mathcal{F}^{\prime}_{1}\leftarrow\mathcal{F}_{1},\mathcal{F}_{2}^{\prime}\leftarrow\mathcal{F}_{2}$.

9: end if

10: if $P$ is not an augmenting path for clean matroids then

11: find the first edge on $P$ such that $e\notin D(X)$ via _binary search_.
Add corresponding set to $\mathcal{F}_{1}$ or $\mathcal{F}_{2}$ and go to Line
3.

12: end if

Here, $D_{d}^{\mathcal{F}}(X)$ is the bipartite exchange graph for the dirty
matroids $\mathcal{M}^{1}_{d}$ and $\mathcal{M}^{2}_{d}$, in which we have
excluded the list of false queries $\mathcal{F}$. More formally, for every
$x\in X$ and $y\in E\setminus X$ there is an edge $(x,y)$ in
$D_{d}^{\mathcal{F}}(X)$ if $X-x+y\in\mathcal{I}_{1}$ and
$X-x+y\notin\mathcal{F}_{1}$ and there is an edge $(y,x)$ in
$D_{d}^{\mathcal{F}}(X)$ if $X-x+y\in\mathcal{I}_{2}$ and
$X-x+y\notin\mathcal{F}_{2}$.

Next, we analyze this augmenting path algorithm. In order to define an error
measure, let $\eta_{1}=\\{F\in\mathcal{I}_{d}^{1}\mid
F\notin\mathcal{I}^{1}\\}$ and $\eta_{2}=\\{F\in\mathcal{I}_{d}^{2}\mid
F\notin\mathcal{I}^{2}\\}$ be the number of different sets which are
independent in the dirty matroid but not independent in the clean matroid. We
now show the following result, which is stronger than Proposition 4.2.

######  Proposition A.1.

Let $\mathcal{M}^{1}$ and $\mathcal{M}^{2}$ be two partition matroids and
$\mathcal{M}^{1}_{d}$ and $\mathcal{M}^{2}_{d}$ be two dirty matroids such
that $\mathcal{M}^{1}_{d}$ and $\mathcal{M}^{2}_{d}$ are supersets of
$\mathcal{M}^{1}$ and $\mathcal{M}^{2}$, respectively. Given a feasible
solution $X\in\mathcal{I}^{1}\cap\mathcal{I}^{2}$ of value $k$, there is an
algorithm that either returns a solution of value $k+1$ or outputs that $X$ is
maximum using at most $2+(\eta_{1}+\eta_{2})\cdot(\lceil\log_{2}(n)\rceil+2)$
clean oracle calls.

Moreover, there is an algorithm that computes an optimum solution for matroid
intersection using at most
$(r+1)\cdot(2+(\eta_{1}+\eta_{2})\cdot(\lceil\log_{2}(n)\rceil+2))$ clean
oracle calls.

###### Proof.

We first prove that the solution output by the algorithm is feasible. If there
is no augmenting path in $D_{d}^{\mathcal{F}}(X)$, then there is no augmenting
path in $D(X)$ since the dirty matroids are supersets of the clean matroids
and in $\mathcal{F}_{1}$ and $\mathcal{F}_{2}$ we only save queries which are
not independent in the clean matroid. Once we find an augmenting path $P$ in
$D_{d}^{\mathcal{F}}(X)$, we always verify it using two clean oracle calls: We
query if $X\Delta P$ is independent in $\mathcal{M}_{1}$ and in
$\mathcal{M}_{2}$. Hence, we only augment $X$ if the augmenting path $P$ is
also an augmenting path in $D(X)$. Since both clean matroids are partition
matroids, we do not need to verify that $P$ is an augmenting path without
chords and hence $X\Delta P$ is an independent set in both clean matroids.

It remains to prove that we use at most
$2+(\eta_{1}+\eta_{2})\cdot\lceil\log_{2}(n)\rceil$ clean oracle calls. As
described above, after finding an augmenting path $P$ in
$D_{d}^{\mathcal{F}}(X)$, we verify it using two clean oracle calls: We query
if $X\Delta P$ is independent in $\mathcal{M}_{1}$ and in $\mathcal{M}_{2}$.
If it is independent, we are done. This check needs 2 clean oracle calls.
Otherwise, one of the queries tells us that $X\Delta P$ is not independent,
i.e., one of the edges $e$ in $P$ corresponds to a resulting set $X_{e}$ such
that $X_{e}$ is independent in, say $\mathcal{M}_{d}^{1}$, but not independent
in $\mathcal{M}^{1}$. In particular, in this case Line 11 is executed.

We now show the following: Whenever Line 11 is executed, we add to
$\mathcal{F}_{1}$ or $\mathcal{F}_{2}$ an additional set and we can find such
a set using at most $\log_{2}(n)$ many clean oracle calls. Since
$|\mathcal{F}_{1}|+|\mathcal{F}_{2}|\leq\eta_{1}+\eta_{2}$ by definition, this
shows the desired bound.

The exchange graph $D(X)$ is a subgraph of the exchange graph
$D_{d}^{\mathcal{F}}(X)$ since the dirty matroids are supersets of the clean
matroid and by definition of $\mathcal{F}_{1}$ and $\mathcal{F}_{2}$. Hence,
if $P=e_{1},e_{2},...,e_{p}$ is an augmenting path in $D_{d}^{\mathcal{F}}(X)$
but not an augmenting path in $D(X)$, there must be an edge $e_{i}\in P$ which
is not in $D(X)$. Let $e_{i}$ be the first such edge. In order to find
$e_{i}$, we simply do a binary search: In each iteration, we have two pointers
$\ell$ and $r$, satisfying $0\leq\ell\leq i$ and $i\leq r\leq p$, for which we
know that the first $\ell$ edges of $P$ are also in $D(X)$ and among the edges
$e_{\ell+1},...,e_{r}$ there must be an edge which is not in $D(X)$. Then, for
$P^{\prime}=e_{1},e_{2},...,e_{\ell+\lfloor\frac{r-\ell}{2}\rfloor}$ we simply
query if $X\Delta P^{\prime}$ is independent in both clean matroids. If yes,
then we set $\ell=\ell+\lfloor\frac{r-\ell}{2}\rfloor$. If no, we set
$r=\ell+\lfloor\frac{r-\ell}{2}\rfloor$. We repeat this until we found
$e_{i}$. This binary search algorithm finds the first edge $e\in P$ which is
not in $D(X)$ using at most $\lceil\log_{2}(n)\rceil$ many clean oracle calls,
where $n$ is the number of elements $|E|$. The additional $+2$ in the bound
appears since whenever we compute a new candidate augmenting path $P$, we
first test if it is also an augmenting path in $D(X)$ using 2 clean oracle
calls. Therefore, we obtain the bound of at most
$2+(\eta_{1}+\eta_{2})\cdot(\lceil\log_{2}(n)\rceil+2)$ clean oracle calls.

We obtain the final bound of
$(r+1)\cdot(2+(\eta_{1}+\eta_{2})\cdot(\lceil\log_{2}(n)\rceil+2))$ clean
oracle calls for computing an optimum solution for matroid intersection as
follows: In each iteration we increase the size of the current solution by one
or prove that there is no improvement possible (and hence the solution is
optimal). Therefore, there are at most $r+1$ iterations, which proves the
bound. ∎

####  A.2.2 Matroid Intersection via Warm-Starting using a Dirty Solution

In this subsection we consider the task of using a solution to the dirty
matroid intersection instance as a “warm-start” for the clean matroid
intersection instance. In particular, we compute a maximal subset of the dirty
solution using only few clean oracle calls, which again will depend on the
error of the dirty matroids. Similar approaches for warm-starting using
predictions have been used in [14, 9, 31] for problems like weighted bipartite
matching or weighted matroid intersection. We show here that this is also
possible using dirty matroids.

Before we start with the algorithm, let us define our error measure for this
subsection. Here, we are just interested in the removal error: for a given
maximum solution $S_{d}$ for the dirty matroid intersection, we compute the
shortest distance to obtain a feasible solution to the clean matroid
intersection problem. Then, the error is simply the maximum value of this
shortest distance among all maximum solutions $S_{d}$ for the dirty matroid
intersection. More formally, let
$s_{d}^{*}=\max_{S_{d}\in\mathcal{I}^{1}_{d}\cap\mathcal{I}^{2}_{d}}|S_{d}|$
and define
$\mathcal{S}_{d}^{*}=\\{S_{d}\in\mathcal{I}^{1}_{d}\cap\mathcal{I}^{2}_{d}\mid|S_{d}|=s_{d}^{*}\\}$
to be the set of optimum solutions to the dirty matroid intersection problem.
We define
$\eta_{r}=\max_{S_{d}\in\mathcal{S}_{d}^{*}}\min_{S_{c}\in\mathcal{I}^{1}\cap\mathcal{I}^{2}}\\{|S_{d}\setminus
S_{c}|:S_{c}\subseteq S_{d}\\}$.

Our algorithm works as follows. We first compute a maximum solution
$S_{d}\in\mathcal{I}^{1}_{d}\cap\mathcal{I}^{2}_{d}$ using some algorithm for
matroid intersection. Then, via binary search we greedily remove elements to
first obtain a solution which is in $\mathcal{I}^{1}$, and then do the same to
obtain a solution which is also in $\mathcal{I}^{2}$. We will then show that
this solution satisfies $|S_{c}^{\prime}|\geq|S_{d}|-2\eta_{r}$ and that we
use at most $2+2\eta_{r}\cdot(1+\lceil\log_{2}(n)\rceil)$ many clean oracle
calls to compute $S_{c}^{\prime}$.

Algorithm 5 Obtaining a Warm-Start Solution

1: Input: Two dirty and clean matroids.

2: Output: A feasible solution
$S_{c}^{\prime}\in\mathcal{I}^{1}\cap\mathcal{I}^{2}$.

3: Compute maximum-cardinality solution
$S_{d}\in\mathcal{I}^{1}_{d}\cap\mathcal{I}^{2}_{d}$

4: for $i=1,2$ do

5: if $S_{d}\in\mathcal{I}^{i}$ then

6: go to Line 4 with $i=2$ or return $S_{c}^{\prime}=S_{d}$ if $i=2$

7: else

8: sort elements in $S_{d}$ in arbitrary order $e_{1},e_{2},...,e_{|S_{d}|}$.

9: find the first element $e_{j}\in S_{d}$ such that
$\\{e_{1},...,e_{j-1}\\}\in\mathcal{I}^{i}$ and
$\\{e_{1},...,e_{j}\\}\notin\mathcal{I}^{i}$ via _binary search_. Set
$S_{d}=S_{d}-e_{j}$ and go to Line 5.

10: end if

11: end for

See 4.3

###### Proof.

Feasibility is clear since we check in Line 5 for both matroids whether the
solution is indeed feasible. We first prove that we remove at most $2\eta_{r}$
many elements from $S_{d}$ to obtain a feasible solution
$S_{c}^{\prime}\in\mathcal{I}^{1}\cap\mathcal{I}^{2}$. By the definition of
the error $\eta_{r}$, there is some set
$S_{c}\in\mathcal{I}^{1}\cap\mathcal{I}^{2}$ with $S_{c}\subseteq S_{d}$ of
size $|S_{d}|-\eta_{r}$. Hence, there is some set $R_{\eta}^{1}$ such that
$S_{d}\setminus R_{\eta}^{1}\in\mathcal{I}^{1}$ and some set $R_{\eta}^{2}$
such that $S_{d}\setminus R_{\eta}^{2}\in\mathcal{I}^{2}$, where
$|R_{\eta}^{1}|\leq\eta_{r}$ and $|R_{\eta}^{2}|\leq\eta_{r}$. Therefore,
$S_{c}^{\prime}\coloneqq S_{d}\setminus(R_{\eta}^{1}\cup
R_{\eta}^{2})\in\mathcal{I}^{1}\cap\mathcal{I}^{2}$ and
$|S_{c}^{\prime}|\geq|S_{d}|-2\eta_{r}$. Note that since $\mathcal{M}^{1}$ and
$\mathcal{M}^{2}$ are matroids, the set $R_{\eta}^{1}$ can be found by
greedily removing elements from $S_{d}$ such that $S_{d}\setminus
R_{\eta}^{1}\in\mathcal{I}^{1}$ and, afterwards, the set $R_{\eta}^{2}$ can be
found by greedily removing elements from $S_{d}\setminus R_{\eta}^{1}$ such
that $(S_{d}\setminus R_{\eta}^{1})\setminus R_{\eta}^{2}\in\mathcal{I}^{2}$.
Since Algorithm 5 computes such a set, we conclude that Line 7 is executed at
most $2\eta_{r}$ times.

Next, we show that whenever Line 7 is executed, we use at most
$\lceil\log_{2}(n)\rceil$ many clean oracle calls. We fix some
$i\in\\{1,2\\}$. Let $e_{1},e_{2},...,e_{|S_{d}|}$ be any order of the
elements. To find the first element $e_{j}\in S_{d}$ such that
$\\{e_{1},...,e_{j-1}\\}\in\mathcal{I}^{i}$ and
$\\{e_{1},...,e_{j}\\}\notin\mathcal{I}^{i}$, the algorithm performs a binary
search. By folklore results, we use at most $\lceil\log_{2}(n)\rceil$ many
clean oracle calls to do so. Furthermore, whenever Line 7 is executed, we have