\section{Introduction}
Dealing with uncertainty
is a common challenge
in many real-world settings. The research area
of \emph{explorable uncertainty}
\cite{kahan91queries,erlebach15querysurvey}
considers such scenarios assuming that, for
any uncertain input element, a \emph{query} can be used to obtain
the exact value of that element. The uncertain input value
is often represented by an interval that
contains the exact
value, and a query returns that exact value.
Queries are costly, and hence the goal is to make as few queries as possible
until sufficient information has been obtained to solve the given
problem. The major challenge is to balance the resulting exploration-exploitation tradeoff. 
For all problems that we consider, there exist input instances that are impossible to solve without querying the entire input. Therefore, instead of aiming to derive absolute bounds on the number of queries required for an input of size~$n$ in the worst case, we use 
competitive analysis to compare the number of queries
made by an algorithm with the
minimum number of queries among all feasible solutions, i.e., we aim for query-competitive algorithms.


In this query model, we consider very fundamental problems  that underlie numerous
applications: sorting, computing the minimum element, and computing
a minimum spanning tree in a graph with uncertain edge weights.
These problems
are well understood in the setting of explorable uncertainty: The best
known deterministic algorithms are $2$-competitive and no deterministic algorithm can be better \cite{erlebach08steiner_uncertainty,megow17mst,halldorsson19sortingqueries,kahan91queries}.
For the sorting and minimum problems,
we consider the setting where we want to solve the problem
for a number of different, possibly overlapping subsets of a
given ground set of uncertain elements. Such settings can be
motivated e.g.\ by distributed database caches~\cite{olston2000queries}
where one wants to answer database queries using cached local data
and a minimum number of queries to the master database.
Interestingly, these problems can also be phrased as (hyper)graph orientation problems, where the goal is to orient each (hyper)edge towards its minimum-weight vertex~\cite{BampisDEdLMS21}.
The minimum spanning tree (MST) problem is one of the most fundamental combinatorial
problems.
It is among the most widely studied problems in computing with
explorable uncertainty and has been a cornerstone in the
development of algorithmic approaches as well as lower
bound techniques \cite{erlebach08steiner_uncertainty,erlebach15querysurvey,megow17mst}.

Instead of assuming that no information about an uncertain
value is available except for the interval in which it is contained,
we study
a setting 
where predictions for the uncertain values are available.
For example, machine learning (ML) methods could be used to predict the value
of an interval.
Given the tremendous progress in artificial intelligence and ML in recent decades, we can expect that those predictions are of good accuracy but there is no guarantee and the predictions might be completely wrong.
This lack of provable performance guarantees for ML
often causes concerns regarding how confident one can be that
an ML algorithm will perform sufficiently well in all circumstances.
In many settings, e.g., safety-critical applications,
having provable performance guarantees is highly desirable or
even obligatory.
It is a very natural question
whether the availability of such (ML) predictions can be exploited by query 
algorithms for computing with explorable uncertainty.
Ideally, an algorithm should perform very well if
predictions are accurate, but even if they are arbitrarily
wrong, the algorithm should not perform worse than an algorithm
that handles the problem without access to predictions.
To emphasize
that the predictions can be wrong, we refer to them
as \emph{untrusted predictions}.

We note that the availability of both uncertainty intervals and
untrusted predictions is natural in many scenarios. For example,
a known past location and maximum movement speed of a mobile node
yield an uncertainty interval that is guaranteed to contain the
current location, while a ML method may predict
the node's precise location based on past movement data.
Similarly, in a distributed database system where the master database
updates a value in the local database only if the new value is outside
a fixed interval around the previously stored value, we have an
interval that is guaranteed to contain the current value while
a ML method may predict the precise current value
based on past time series data.

We study for the first time the combination of
explorable uncertainty and untrusted predictions. Our work draws inspiration
from recent work that has considered untrusted predictions in the context
of online algorithms, where the input is revealed to an algorithm incrementally
and the algorithm must make decisions without knowledge of future inputs.
We adopt the notions of $\alpha$-consistency
and $\beta$-robustness~\cite{lykouris2018competitive,purohit2018improving}: 
An algorithm is $\alpha$-consistent if it
is $\alpha$-competitive when the predictions are correct, and it is
$\beta$-robust if it is $\beta$-competitive no matter how wrong the
predictions are. Furthermore, we are interested in a smooth transition
between the case with correct predictions and the case with arbitrarily
incorrect predictions: We aim for performance guarantees
that degrade gracefully with the \emph{amount} of prediction error.
This raises interesting questions regarding appropriate ways of
measuring prediction errors, and we explore several such measures.

Our results show that, in the setting of explorable uncertainty,
it is in fact possible to exploit ML predictions of the uncertain
values in such a way that the performance of an algorithm is improved
when the predictions are good, while at the same time a strong bound
on the worst-case performance can be guaranteed even when the predictions
are arbitrarily bad. Following this approach, ML can thus be embedded within a
system to improve the typical performance while still maintaining
provable worst-case guarantees. In this way users can be shielded from
occasional failures of the ML algorithms.
Therefore, our approach contributes methods and analysis techniques
that can help to address the challenge of building trustable AI systems.

\paragraph{Main results} We show how to
utilize (possibly machine-learned) predictions in a query-based model for computing under uncertainty and prove worst-case performance guarantees. Our major contribution is twofold: 
\begin{inparaitem}
\item[(a)] we prove that untrusted predictions can circumvent lower bounds in the context of explorable uncertainty, and 
\item[(b)] we provide new structural insights for previously studied, fundamental problems that might be useful regardless of predictions.
\end{inparaitem}
Finally, we conduct experiments that show that our algorithms are practical and that confirm the theoretical improvement.

For the problems of {sorting or identifying minima in intersecting sets}
and finding an MST,
we give algorithms that are $1.5$-consistent
and $2$-robust, and show that this is the best possible consistency when aiming for optimal robustness. 
It is worth noting that our algorithms achieve the
improved competitive ratio of $1.5$ in case of accurate predictions
while maintaining the worst-case ratio of~$2$. This is in contrast
to work on other online problems with predictions where the exploitation
of predictions usually incurs an increase in the worst-case
ratio (see, e.g, \cite{purohit2018improving,AntoniadisGKK20}).
We also give a parameterized {robustness-consistency} tradeoff.
Our major focus lies on a more fine-grained performance analysis
with guarantees that improve with the accuracy of the predictions.
We compare three different measures $k_{\#}, k_h, k_M$ for the prediction accuracy. The number of inaccurate predictions $k_{\#}$ is
too crude to allow for a performance improving on the lower bounds of~$2$ for the setting without predictions~\cite{erlebach08steiner_uncertainty,kahan91queries}.
We propose two measures that take structural insights about uncertainty intervals into account, the hop distance $k_h$ and the mandatory query distance $k_M$. The latter can be proven to be more restrictive,~i.e.,~$k_M\leq k_h$. We give proper definitions later. While the hop distance $k_h$ is very intuitive and possibly of general interest, the mandatory query distance $k_M$ is tailored to problems with explorable uncertainty.
We show that the predictions are PAC-learnable w.r.t.~both error measures, $k_h$ and~$k_M$.

For the problem of identifying the minima in intersecting sets, we provide an algorithm with competitive ratio $\min\{(1+\frac{1}{\gamma-1})(1+ \frac{k_M}{\mathrm{opt}}), \gamma \}$, for any integral $\gamma\geq 2$. Here, $\mathrm{opt}$ is the minimum number of queries in an offline solution; precise definitions are given below. This is best possible for $k_M{=0}$ {and large $k_M$}. With respect to the hop distance, we achieve the stronger bound $\min\{(1+\frac{1}{\gamma})(1+ \frac{k_h}{\mathrm{opt}}), \gamma\}$, for any integral $\gamma \geq 2$, which is also best possible for $k_h = 0$ and large $k_h$. It is not difficult to see that the sorting problem can be reduced to the minimum problem by creating a set for each pair of elements that are in the same set of the sorting instance, so these bounds also apply to the sorting problem. For the special case of sorting a single set, we obtain an algorithm with competitive ratio $\min\{1+k/\mathrm{opt}, 2\}$ for any of the considered accuracy measures, which is best possible.
Finding the MST under uncertainty is the combinatorially most challenging problem. As our main result, we give an algorithm with competitive ratio $\min\{ 1+ \frac{1}{\gamma} +  (5 + \frac{1}{\gamma}) \cdot \frac{k_h}{\mathrm{opt}}, \max\{3,\gamma + \frac{1}{\mathrm{opt}}\}\}$, for any integral $\gamma \geq 2$.
All our algorithms have polynomial running time except the algorithms for the minimum problem, which may involve solving an NP-hard vertex cover problem. We justify this complexity by showing that even the offline variant of the minimum problem is NP-hard.

Omitted proofs are provided in the appendix.


\paragraph{Further related work}
There is a long history of research on the tradeoff between exploration and exploitation when coping with uncertainty in the input data. Stochastic models are often assumed,
e.g., in work on multi-armed bandits~\cite{Thompson33,BubeckC12,GittinsGW11-book}, Weitzman's Pandora's box problem \cite{Weitzman1979}, and more recently query-variants of combinatorial optimization problems; {see, e.g.,
\cite{singla2018price,gupta2019markovian}, and specific problems such as stochastic knapsack~\cite{DeanGV08,Ma18}, orienteering~\cite{GuptaKNR15,BansalN15}, matching~\cite{ChenIKMR09,BansalGLMNR12,BlumDHPSS20,BehnezhadFHR19,AssadiKL19}, and probing problems \cite{AdamczykSW16,GuptaN13,GuptaNS16}.}

In our work, we assume no knowledge of stochastic information and aim for robust algorithms that perform well even in a worst case. This line of research on (adversarial) explorable uncertainty has been initiated by Kahan~\cite{kahan91queries} in the context of selection problems.
In particular, he showed for the problem of identifying all maximum elements of a set of uncertain
values that querying the intervals in order of non-increasing right endpoints
requires at most one more query {than} the optimal query set.
Subsequent work addressed finding the~$k$-th smallest value in a set of uncertainty intervals~\cite{gupta16queryselection,feder03medianqueries},
caching problems
\cite{olston2000queries}, computing a function value~\cite{khanna01queries}, sorting~\cite{halldorsson19sortingqueries}, and
combinatorial optimization problems, such as shortest path~\cite{feder07pathsqueires}, the knapsack problem~\cite{goerigk15knapsackqueries}, scheduling problems~\cite{DurrEMM20,arantes18schedulingqueries,albersE2020}, the MST problem and matroids~\cite{erlebach08steiner_uncertainty,erlebach14mstverification,megow17mst,focke17mstexp,MerinoS19}. 

Most related to our work are previous results on the MST problem and sorting with explorable uncertainty.
For the MST problem with uncertain edge weights represented by open intervals, a $2$-competitive
deterministic algorithm was presented and shown to be best possible~\cite{erlebach08steiner_uncertainty}.
The algorithm is based on the concept of \emph{witness sets}, i.e., sets of uncertain elements
with the property that any feasible query set must query at least one element of the set. The algorithm
from~\cite{erlebach08steiner_uncertainty} repeatedly
identifies a witness set of size~$2$ that corresponds to two candidates for the maximum-weight edge
in a cycle of the given graph, and queries both its elements. It is also known that randomization admits 
an improved competitive ratio of $1.707$ for the MST problem with uncertainty~\cite{megow17mst}. {Both, a deterministic $2$-competitive algorithm and a randomized $1.707$-competitive algorithm, are known for the more general problem of finding the minimum base in a matroid~\cite{erlebach16cheapestset,megow17mst}, even for the case with non-uniform query costs~\cite{megow17mst}.}
For sorting a single set, a $2$-competitive algorithm exists (even
with arbitrary query costs) and is
best possible~\cite{halldorsson19sortingqueries}. In the case of uniform query costs, the algorithm simply queries witness
sets of size~$2$; in the case of arbitrary costs, it first queries a minimum-weight vertex cover of the interval
graph corresponding to the instance and then executes any remaining queries that are still necessary.
For uniform query cost, the competitive ratio can be improved to~$1.5$ using randomization~\cite{halldorsson19sortingqueries}.

Our work is the first to consider explorable uncertainty in the recently proposed framework of online algorithms using (machine-learned) predictions \cite{medina2017revenue,purohit2018improving,lykouris2018competitive}. After work on revenue optimization~\cite{medina2017revenue} and online caching~\cite{lykouris2018competitive}, Kumar et al.~\cite{purohit2018improving} studied online algorithms with respect to consistency and robustness in the context of classical online problems, ski-rental and non-clairvoyant scheduling. They also studied the performance as a function of the prediction error. This work initiated a vast growing line of research. Studied problems include rent-or-buy problems \cite{purohit2018improving,GollapudiP19,WeiZ20}, revenue optimization~\cite{medina2017revenue},
	scheduling and bin packing~\cite{purohit2018improving,angelopoulos2019online,moseley2020online,Mitzenmacher20,AzarLT2021,LattanziLMV20}, caching and metrical task systems~\cite{lykouris2018competitive,rohatgi2019near,AntoniadisCEPS2020,Wei20}, matching~\cite{KumarPSSV19,AntoniadisGKK20} and secretary problems~\cite{DuettingLLV21,AntoniadisGKK20}. Very recently and in a similar spirit as our work, Lu et al.~\cite{LuRSZ2021} studied a generalized sorting problem with additional predictions. Their model strictly differs from ours, as they focus on bounds for the absolute number of pair-wise comparisons whereas we aim for query-competitive algorithms.
Overall, learning-augmented online optimization is a highly topical concept which has not yet been studied in the explorable uncertainty model.

There is a significant body of work on computing in models where information
about a hidden object can be accessed only via queries. The 
hidden object can for example be a function, a matrix, or a graph.
In the graph context, property testing~\cite{Goldreich2017} has been studied extensively
since the early 1990s. A typical problem is to decide
whether a given graph has a certain property or is ``far'' from having that
property using a small (sublinear or even constant) number of queries that look
up entries of the adjacency matrix of the graph.
Many other types of queries have
been studied (see e.g.~\cite{Mazzawi2010,Beame2018,Rubinstein2018,Chen2020,Assadi2020} and many more).
Such work has often considered graph reconstruction problems or
parameter estimation problems (e.g., estimating the number of edges).
The bounds on the number of queries made by an algorithm that have been shown
in these problems are usually absolute, i.e., given as a function of the input size,
but independent of the input graph itself, and the resulting correctness guarantees
are often probabilistic.

In contrast to much of the work on algorithms with query access to a hidden
object, we evaluate our algorithms in an instance-dependent manner: For each
input, we compare the number of queries made by an algorithm with the best
possible number of queries \emph{for that input}, using competitive analysis.
In computing with uncertainty, there are typically inputs where even an
optimal query set has to query essentially the whole input in order to be
able to solve the problem, hence absolute bounds on the number of queries
depending only on the size of the input would often be trivial. The goal
is hence to devise algorithms that use, on each input, a number of queries
that is not much larger than the optimal query set for that input.


\section{{Definitions, accuracy of predictions, and lower bounds}}
\label{sec:prelim}
\paragraph{Problem definitions} In the \emph{minimum problem under uncertainty}, we are given a set $\mathcal{I}$ of $n$ uncertainty intervals with a predicted value $\pred{w}_i\in I_i$ for each $I_i \in \mathcal{I}$, and a family $\mathcal{S}$ of $m$ subsets of $\mathcal{I}$.
The \emph{true} value of interval $I_i$ is denoted by $w_i$ and can be revealed by a \emph{query}.
The task is to identify for each $S \in \mathcal{S}$ the element with the minimum true value. Note that this may not require to determine the actual value of this element.

The {\em sorting problem under uncertainty} is closely related to the minimum problem. For the same input, the task is to sort, for each set $S \in \mathcal{S}$, the intervals in non-decreasing order of their true values.
	
In the {\em minimum spanning tree (MST) problem under uncertainty}, we are given a graph $G=(V,E)$, with uncertainty intervals $I_e$
and predicted values $\pred{w}_e \in I_e$ for the weight of each edge $e \in E$. A minimum spanning tree (MST) is a tree that connects all vertices of $G$ at a minimum total edge weight.
The task is to find an MST with respect to the true values of the edge weights.

In all three problems, the goal is to solve the task using a minimum number of queries. 
Note that the exact value of a solution, i.e., the minimum value or the weight of the MST, does not need to be determined. 
We further assume that each uncertainty interval is either trivial or open, i.e., $I_i = (L_i,U_i)$ or $I_i = \{w_i\}$,  
as otherwise a simple lower bound of $n$ on the competitive ratio exists for the minimum and MST problems~\cite{gupta16queryselection}.

Further, we study \emph{adaptive
strategies} that make queries sequentially and utilize the results of previous steps to decide upon the next query.
We impose no time/space complexity constraints on the algorithms, as we are interested in understanding the competitive ratio of the problems.
We assume the algorithms never query intervals that are trivial or that were previously queried.
A set $W$ of queries is called a \emph{witness set} \cite{bruce05uncertainty,erlebach08steiner_uncertainty} if every feasible solution (i.e., every set of queries that solves the problem) contains at least one query in~$W$.

\paragraph{Competitive analysis}
We employ competitive analysis and compare the outcome of our algorithms with the best offline solution, i.e., the minimum number of queries needed to verify a solution when all values are known in advance. We call the offline variants of our problems \emph{verification problems}.
{By $\mathrm{OPT}$ we denote an arbitrary optimal query set for the verification problem, and by $\mathrm{opt}$ its cardinality.
For an algorithm for the online problem, we denote by $\mathrm{ALG}$ the set of queries it makes and by $|\mathrm{ALG}|$ the cardinality of that set.}
An algorithm is $\rho$-{\em competitive} if it executes, for any problem instance, at most $\rho \cdot {\mathrm{opt}}$ queries.
Further, we quantify the performance of our algorithms depending on the quality of predictions. For the extreme cases, we say that an algorithm is $\alpha$-\emph{consistent} if it is $\alpha$-competitive if the predictions are correct, and $\beta$-\emph{robust} if it is $\beta$-competitive if the predictions are inaccurate. 

Clearly, an algorithm that assumes the predicted values to be correct and solves the verification problem is $1$-consistent. However, such an algorithm may have an arbitrarily bad performance if the predictions are incorrect. Similarly, the known deterministic $2$-competitive algorithms for the online problems without predictions~\cite{erlebach08steiner_uncertainty, kahan91queries} are $2$-robust and $2$-consistent. The known lower bounds of $2$ rule out any robustness factor less than $2$ for our model. They build on the following simple example with two intersecting intervals $I_a,I_b$. No matter which interval a deterministic algorithm queries first, say $I_a$, the realized value could be $w_a\in I_a\cap I_b$, which requires a second query. If the adversary chooses $w_b\notin I_a\cap I_b$, querying just $I_b$ would have been sufficient to identify the minimal interval.

We give a bound on the best~achievable~tradeoff between consistency and robustness. Later, we will  provide algorithms with matching performance guarantees.

\begin{restatable}{theorem}{ThmLBTradeoffWithoutError}
\label{theo_minimum_combined_lb}
  Let $\beta \geq 2$ be a fixed integer.
  For the minimum (even in a single set), sorting and MST problems under uncertainty, there is no deterministic $\beta$-robust algorithm that is $\alpha$-consistent for $\alpha < 1 + \frac{1}{\beta}$. {And vice versa, no deterministic $\alpha$-consistent algorithm, with $\alpha>1$, is $\beta$-robust for $\beta < \max\{\frac{1}{\alpha-1},2\}$.}
\end{restatable}

\paragraph{Accuracy of predictions}
We aim for a more fine-grained performance analysis giving guarantees that depend on the quality of predictions.
A very natural, simple error measure is the number of inaccurate predictions $k_\#=|\{I_i \in \mathcal{I}\,|\, w_i \not= \w_i\}|$. However, we show that for $k_{\#} \geq 1$ the competitive ratio cannot be better than the known lower bounds of~$2$.
The reason for the weakness of this measure is that it completely ignores 
the interleaving  structure of intervals. (Similarly, using an $L_1$ error metric such as
$\sum_{I_i\in \mathcal{I}}|w_i - \w_i|$ would not be meaningful because only
the \emph{order} of the values and the interval endpoints matters for our problems.)
To address this, we consider {two refined measures for the predictor quality}.

 \emph{Hop distance.} This metric captures naturally the relation between a predicted and a true value in relation to other intervals. 
For a non-trivial interval $I_j=(L_j,U_j)$,
we say that the value of interval $I_i$ \emph{passes over} $L_j$ if one of $w_i,\w_i$ is
$\le L_j$ and the other is $>L_j$. Similarly,
the value of $I_i$ \emph{passes over} $U_j$ if one of $w_i,\w_i$ is
$< U_j$ and the other is $\ge U_j$. Intuitively, the value of $I_i$ passes over one endpoint of~$I_j$
if it enters or leaves $I_j$, and it passes over both endpoints of $I_j$ if it jumps over $I_j$
when going from predicted to true values.
For a trivial interval $I_j=\{w_j\}$, we say that the value of $I_i$
\emph{jumps over}~$I_j$ if one of $w_i,\w_i$ is strictly smaller than $w_j$ and the other is strictly
larger than $w_j$.
{To avoid counting values passing over endpoints of irrelevant intervals,} 
let $A_i$ be the set of intervals that potentially interact with $I_i$.
For the minimum and the sorting problem, we let $A_i$ be the union of all sets that contain $I_i$. When
considering the MST problem, we consider the maximal biconnected component containing $I_i$, i.e., $A_i$
is the union of all intervals on cycles containing~$I_i$.
Now define $h_i=h_i(A_i)$ to be the number of non-trivial intervals $I_j\in A_i$ such that the value of~$I_i$ passes
over $L_j$ plus the number of non-trivial intervals $I_j\in A_i$ such that the value of~$I_i$ passes
over $U_j$, plus the number of trivial intervals $I_j=\{w_j\}$ in $A_i$ such that
the value of $I_i$ jumps over~$I_j$.
The hop distance of a given instance is then $k_h = \sum_{i=1}^n h_i$; 
see also Figure~\ref{fig_hop_ex}.
Note that $k_{\#} = 0$ implies $k_h = 0$, so Theorem~\ref{theo_minimum_combined_lb} implies that no algorithm can simultaneously have competitive ratio better than $1 + \frac{1}{\beta}$ if $k_h = 0$ and $\beta$ for arbitrary~$k_h$.

\begin{figure}[t]
	\centering
\subfigure[]{\label{fig_hop_ex}
	\begin{tikzpicture}[line width = 0.3mm, scale = 0.9, transform shape]	
	\intervalpr{$I_1$}{0}{4}{1.5}{1}{2.75}	
	\intervalpr{$I_2$}{1.5}{6}{2.25}{4.5}{2}	
	\intervalpr{$I_3$}{2.5}{6}{3}{4.5}{5.5}							
	\intervalpr{$I_4$}{3}{6}{3.75}{3.25}{3.75}		
	
	\begin{scope}[on background layer]
	\draw[line width = 0.2mm,,lightgray] (0,1) -- (0,4);
	\draw[line width = 0.2mm,,lightgray] (1.5,1) -- (1.5,4);
	\draw[line width = 0.2mm,,lightgray] (2.5,1) -- (2.5,4);
	\draw[line width = 0.2mm,,lightgray] (3,1) -- (3,4);
	\draw[line width = 0.2mm,,lightgray] (6,1) -- (6,4);
	\draw[line width = 0.2mm,,lightgray] (4,1) -- (4,4);
	\end{scope}
	
	\draw[decoration= {brace, amplitude = 5 pt, aspect = 0.5}, decorate] (2.75,1.3) -- (1,1.3);
	\node[] (l1) at (1.85,1) {\scalebox{0.75}{$h_1=2$}};
	
	\draw[decoration= {brace, amplitude = 5 pt, aspect = 0.5}, decorate] (4.5,2.1) -- (2,2.1);
	\node[] (l1) at (3.2,1.8) {\scalebox{0.75}{$h_2=3$}};
	
	\draw[decoration= {brace, amplitude = 2.5 pt, aspect = 0.5}, decorate] (5.5,2.85) -- (4.5,2.85);
	\node[] (l1) at (4.95,2.6) {\scalebox{0.75}{$h_3=0$}};
	
	\draw[decoration= {brace, amplitude = 1 pt, aspect = 0.5}, decorate] (3.75,3.6) -- (3.25,3.6);
	\node[] (l1) at (3.5,3.4) {\scalebox{0.75}{$h_4=0$}};
	\end{tikzpicture}
}
\hspace*{2cm}
\subfigure[]{\label{fig_man_ex}
	\begin{tikzpicture}[line width = 0.3mm, scale = 0.9, transform shape]
		\intervalpr{$I_1$}{0}{4}{1.5}{1}{1}		
		\intervalpr{$I_2$}{1.5}{6}{2.25}{3.25}{5.5}		
		\intervalpr{$I_3$}{2.5}{6}{3}{3.25}{5.5}								
		\intervalpr{$I_4$}{3}{6}{3.75}{3.25}{5.5}				
		
	
		\node[] (l1) at (1.85,0.95) {};	
	\end{tikzpicture}
}
\caption{Examples for the minimum problem with a single set $S=\{I_1,I_2,I_3,I_4\}$. Circles illustrate true values and crosses illustrate the predicted values. \subref{fig_hop_ex} Predictions and true values with a total hop distance of $k_h = 5$.
\subref{fig_man_ex} Predictions and true values with a mandatory query distance of $k_M = 1$.
}
\label{fig_error_ex}
\end{figure}

\emph{Mandatory query distance.} While the hop distance takes structural information regarding the interval structure into account, it does not distinguish whether a ``hop'' affects a feasible solution. We introduce a third and strongest measure for the prediction accuracy based on the following definition. 

\begin{definition}[mandatory]
	Given a problem instance with uncertainty intervals, an interval
	is {\em mandatory} if it is in each feasible query set of the verification problem. An interval is {\em prediction mandatory} if it is in each feasible query set assuming that the predictions $\w$ are accurate.
\end{definition}

Let $\mathcal{I}_P$ be the set of prediction mandatory elements, 
and let $\mathcal{I}_R$ be the set of really mandatory elements. 
The 
\emph{mandatory query distance} is the size of the symmetric difference of $\mathcal{I}_P$ and $\mathcal{I}_R$, i.e., $k_M = |\mathcal{I}_P \sym \mathcal{I}_R| = |(\mathcal{I}_P \cup \mathcal{I}_R) \setminus (\mathcal{I}_P \cap \mathcal{I}_R)| = |(\mathcal{I}_P \setminus \mathcal{I}_R) \cup (\mathcal{I}_R \setminus \mathcal{I}_P)|$.
Figure~\ref{fig_man_ex} shows an example with $k_M=1$.
Considering the true values in the example, both $\{I_1\}$ and $\{I_2,I_3,I_4\}$ are feasible solutions. Thus, no element is part of every feasible solution and $\mathcal{I}_R = \emptyset$. 
Assuming correct predicted values, $I_1$ has to be queried even if all other intervals have already been queried and, therefore, $\mathcal{I}_P = \{I_1\}$.
It follows $k_M = |\mathcal{I}_P \sym \mathcal{I}_R| = 1$.

Obviously, $k_M$ is a problem-specific error measure as, in a given set of uncertainty intervals, different intervals may be mandatory for different problems.
We can relate $k_M$ to $k_h$ in the following theorem.
 
\begin{restatable}{theorem}{HopDistanceMandatoryDistance}
	\label{Theo_hop_distance_mandatory_distance}
	For any instance of the minimum, sorting and MST problems under uncertainty, the hop distance is at least as large as the mandatory query distance, $k_M \leq k_h$.
\end{restatable}

We provide a lower bound on the competitive ratio that is stronger than Theorem~\ref{theo_minimum_combined_lb}, and later we give matching algorithms for the minimum and sorting problems.
The choice of $\gamma \geq 2$ is due to the lower bound of $2$ in the robustness for all problems we consider.

\begin{restatable}{theorem}{ThmLBMandQueryDist}
\label{theo_lb_sym_diff}
  Let $\gamma \geq 2$ be a fixed rational value. 
  If a deterministic algorithm for the minimum, sorting or MST problem is
  $\gamma$-robust,
  then it cannot have competitive ratio better than $1 + \frac{1}{\gamma-1}$ for $k_M = 0$.
  Furthermore, if an algorithm has competitive ratio $1 + \frac{1}{\gamma-1}$ for $k_M = 0$, then it cannot be better than
	$\gamma$-robust.
\end{restatable}
 
We conclude the definition and discussion of measures for the prediction accuracy with a simple lower bound on the competitive ratio regardless of any desired robustness.

\begin{restatable}{theorem}{ThmLBAllErrorMeasures}
\label{thm_lb_error_measure}
	Any deterministic algorithm for minimum, sorting or MST under uncertainty has a competitive ratio $\rho\geq \min\{1+\frac{k}{\mathrm{opt}},2\}$, for any error measure $k \in \{k_{\#}, k_M, k_h\}$, even for {disjoint} sets.
\end{restatable}

\paragraph{Learnability of predictions} 
We argue that our assumption of having access to machine-learned predictions is realistic. We do so by proving that the predictions are PAC-learnable w.r.t.~$k_h$ and $k_M$. See Appendix~\ref{sec:learnability} for full proofs.
To show PAC-learnability, we assume that the realization $w$ of true values for $\mathcal{I}$ is i.i.d.~drawn from an unknown distribution $\ensuremath{D}$, and
we can i.i.d.~sample realizations from $\ensuremath{D}$ to obtain a training set.
Let $\ensuremath{\mathcal{H}}$ denote the set of all possible predictions $\pred{w}$, that is, vectors $\pred{w}$ with $\pred{w}_i \in I_i$ for each $I_i \in \mathcal{I}$.
Let $k_h(w,\pred{w})$ denote the hop distance of the predictions $\pred{w}$ for the realization with the true values $w$.
Since $w$ is drawn from $\ensuremath{D}$, the value $k_h(w,\pred{w})$ is a random variable. 
Analogously, we consider $k_M(w,\pred{w})$ with regard to the mandatory query distance.
Our goal is to learn predictions $\pred{w}$ that (approximately) minimize the expected error $\EX_{w \sim \ensuremath{D}}[k_h(w,\pred{w})]$ respectively $\EX_{w \sim \ensuremath{D}}[k_M(w,\pred{w})]$.

For both error measures, we employ the \emph{empirical risk minimization (ERM)} algorithm. ERM first i.i.d.~samples a training set~$S=\{w^1,\ldots,w^m\}$ of~$m$ true value vectors from~$\ensuremath{D}$.
Then, it returns the~$\pred{w} \in \ensuremath{\mathcal{H}}$ that minimizes the \emph{empirical error}~$k_S(\pred{w}) = \frac{1}{m} \sum_{j=1}^{m} k(w^j,\pred{w})$ with $k \in \{k_h,k_m\}$.
We show a polynomial sample complexity $m$ by carefully reducing $\ensuremath{\mathcal{H}}$. The challenging part
is to execute ERM in polynomial time.


\begin{restatable}{theorem}{TheoLearningHop}
	\label{theo_learnability_hop}
	For any~$\eps, \delta \in (0,1)$ and $k \in \{k_h,k_M\}$, there exists a learning algorithm that, using a training set of size~$m$, returns predictions $\pred{w} \in \ensuremath{\mathcal{H}}$, such that
	$\EX_{w \sim \ensuremath{D}}[k(w,\pred{w})] \le \EX_{w \sim \ensuremath{D}}[k(w,\pred{w}^*)] + \eps$ holds with probability at least~$(1-\delta)$, where~$\pred{w}^* = \arg\min_{\pred{w}' \in \ensuremath{\mathcal{H}}} \EX_{w \sim \ensuremath{D}}[k(w,\pred{w}')]$.
	The sample complexity is $m \in \mathcal{O}\left(\frac{(\log(n) - \log(\delta/n))\cdot (2n)^2}{(\eps/n)^2}\right)$ for $k=k_h$, and $m \in \mathcal{O}\left(\frac{(n \cdot \log(n) - \log(\delta))\cdot n^2}{\eps^2}\right)$ otherwise.
	For $k=k_h$, the running time is polynomial in $m$ and $n$.
	Otherwise, the running time is exponential in $n$.
\end{restatable}

Since learning w.r.t.~$\ensuremath{\mathcal{H}}$ and~$k_M$ by using Theorem~\ref{theo_learnability_hop} requires exponential running time, we present an alternative approach.
Instead of showing the learnability of the predicted values, we prove that the set $\mathcal{I}_P$ that leads to the smallest expected error can be learned.
Note that access to only $\mathcal{I}_P$ is sufficient to execute the algorithm for the minimum problem that achieves a competitive ratio depending on $k_M$.
To be more specific, let $\mathcal{P}$ be the power set of $\mathcal{I}$, let $\mathcal{I}_w$ denote the set of mandatory elements for the realization with true values~$w$, and let $k_M(\mathcal{I}_w, P)$ with $P \in \mathcal{P}$ denote the mandatory query distance under the assumption that $\mathcal{I}_P = P$ and $\mathcal{I}_R = \mathcal{I}_w$.
Since $w$ is drawn from $\ensuremath{D}$, the value $\EX_{w \sim \ensuremath{D}}[k_M(\mathcal{I}_w,P)]$ is a random variable.
The mandatory query distance is a problem-specific metric as the characterization of (prediction) mandatory intervals may differ for different problems. We show efficient learnability w.r.t.~$\mathcal{P} $ and~$k_{M}$ for all problems for which $k_M(w,\w)$ can be computed efficiently. This is the case for all problems considered in this paper.
As another argument for learning w.r.t.~$\mathcal{P}$ and $k_M$, we show in Appendix~\ref{sec:learnability} that, for any distribution $D$, the best prediction in $\mathcal{P}$ never has a larger expected error than the best prediction in $\ensuremath{\mathcal{H}}$. The inverse is not true.

\begin{restatable}{theorem}{TheoLearningMan}
	\label{theo_learnability_mandatory}
	For all problems for which $k_M$ can be determined in polynomial time and for
	any~$\eps, \delta \in (0,1)$, there exists a learning algorithm that, using a training set of size~$m  \in \mathcal{O}\left(\frac{(n - \log(\delta))\cdot n^2}{\eps^2}\right),$ returns a predicted set of mandatory intervals $P \in \mathcal{P}$ in time polynomial in~$n$ and~$m$, such that
	$\EX_{w \sim \ensuremath{D}}[k_M(\mathcal{I}_w,P)] \le \EX_{w \sim \ensuremath{D}}[k_M(\mathcal{I}_w,P^*)] + \eps$ holds with probability at least~$(1-\delta)$, where~$P^* = \arg\min_{P' \in \mathcal{P}} \EX_{w \sim \ensuremath{D}}[k_M(\mathcal{I}_w,P')]$.
\end{restatable}


\section{Overview of Techniques}
\label{sec:methods}
Given predicted values for the uncertainty intervals, it is tempting to simply run an optimal offline algorithm~(verification algorithm) under the assumption that the predictions are correct, and to then perform all the queries computed by that verification algorithm.
This is obviously optimal with respect to consistency, but might give arbitrarily bad solutions in the case when the predictions are faulty. 
Instead of blindly following the offline algorithm, we need a strategy to be robust against prediction errors. 
Therefore, we carefully combine structural properties of the problem with {the additional knowledge of untrusted} predictions. 

The crucial structure and unifying concept in all problems under consideration are {\em witness sets}. Witness sets are the key to any comparison with an optimal solution. A ``classical'' witness set is a set of elements for which we can guarantee that any feasible solution must query at least {\em one} of these elements.
Depending on the particular problem, witness sets can be structurally very different (e.g., simply pairs of overlapping intervals for one problem, or sets resulting from a complex consideration of cycles in a certain order for another problem). Nevertheless, in the classical setting without access to predictions, all our problems admit $2$-competitive online algorithms that rely essentially on identifying and querying disjoint witness sets of size two.
We refer to witness sets of size two also as {\em witness pairs}.
While completely relying on querying witness pairs ensures $2$-robustness, it does not lead to any improvements in terms of consistency.
In order to obtain an improved consistency while maintaining optimal or near-optimal robustness, we need to carefully balance the usage of an offline algorithm with the usage of witness sets.

\paragraph{The general framework}
On a high level,
our general algorithmic framework
follows the structure of the offline algorithm: 
In a first stage, it queries elements that are mandatory under the assumption that the predictions are correct.
In a second stage, when no elements are prediction mandatory any more, the algorithm has to decide for each witness pair which of the two elements to query.
If the predictions are correct, the second phase reduces to a vertex cover type problem. 
The following theorem summarizes some of our main results. For minimum and sorting, we show the result by proving the more general Theorem~\ref{thm_minimum:hop} in Section~\ref{sec:minimum} and Appendix~\ref{app:minimum} 
and giving a reduction from the sorting problem to the minimum problem in Section~\ref{sec:sorting}.	For the MST problem, we show the result directly
in Section~\ref{sec:mst} and Appendix~\ref{appx:mst}. 

\begin{theorem}
\label{thm:main1.5-2}
 {For each of the problems, minimum, sorting and MST under uncertainty, there is an algorithm that is $1.5$-consistent and $2$-robust.}
\end{theorem}




During the first phase, just querying prediction mandatory elements can be arbitrarily bad in terms of robustness (cf.\ Theorem~\ref{theo_minimum_combined_lb}).
Thus, given a prediction mandatory element that we wish to query, we query further elements in such a way that they form witness sets. Note that it is not sufficient to augment the set to a ``classical'' size-$2$ witness set (which already might be non-trivial to do for some problems), as this would not yield a performance guarantee better than~$2$ even if the predictions are correct.
Instead, we identify a set of elements for which we can guarantee that at least $2$ out of $3$ of them must be queried by any feasible solution. 
Since we cannot always find such elements based on structural properties alone (otherwise, there would be a $1.5$-competitive algorithm for the problem without predictions), we identify such sets under the assumption that the predictions are correct.
Even after identifying such elements, the algorithm needs to query them in a careful order: If the predictions are wrong, we lose the guarantee on the elements and querying all of them might violate the $2$-robustness.
The first phase of our framework repeatedly identifies such elements and queries them in a careful order while adjusting for potential errors, until no unqueried prediction mandatory elements remain.
Identifying the three elements with the guarantee mentioned above is a major contribution which might be of independent interest regardless of predictions, especially in the context of the MST problem. 
While existing algorithms for MST under uncertainty~\cite{erlebach08steiner_uncertainty,megow17mst} essentially follow the algorithms of Kruskal or Prim and only identify witness sets in the cycle or cut that is currently under consideration, we derive criteria to identify additional witness sets outside the current cycle/cut.
Note that the identification of witness sets and the characterization of (prediction) mandatory intervals are problem specific.
The first phase of our framework differs for the different problems only in the identification of witness sets and (prediction) mandatory elements, and the order in which we query them.

In the second phase, there are no more prediction mandatory elements.
Therefore, the algorithm cannot identify any more ``safe'' queries and, for each witness pair, has to decide which element to query. 
This phase boils down to finding a minimum vertex cover in an auxiliary graph representing
the structure of the witness sets.
In particular, the second phase for the minimum problem and the sorting problem is relatively straightforward and consists of finding and querying a minimum vertex cover.
If the predictions are correct, querying the vertex cover solves the remaining problem with an optimal number of queries. 
Otherwise, additional queries might be necessary, but we can show that this does not violate $2$-robustness.

In the MST problem, wrong predictions can change the vertex cover instance dynamically, and therefore it must be solved in a very careful and adaptive way, requiring substantial additional work. 
Nevertheless, the general framework is the same for all problems.

We remark that the computation of the minimum vertex cover in the second phase is the \emph{only} operation of our algorithms that potentially requires exponential running time. 
For the problems of finding an MST and sorting a single set,
we have to compute a minimum vertex cover in  bipartite and interval graphs, respectively. Both problems are well-known to be polynomial-time solvable. 


\paragraph{Parameterized error-sensitive guarantees} We show how to refine our general framework to achieve error-sensitive and parameterized performance guarantees.
 {We parameterize the first phase as follows: we repeatedly query $\gamma-2$ prediction mandatory elements in addition to the set of three elements of the general framework. The second phase remains unchanged. For both, the minimum problem and sorting, we can bound the error-sensitivity by charging each queried prediction mandatory element that turns out to be not mandatory and each additional query in the second phase to a distinct prediction error in the $k_h$-metric.}
\begin{restatable}{theorem}{thmminimumhop}
	\label{thm_minimum:hop}
	There is an algorithm for the minimum problem under uncertainty that, given an integer parameter $\gamma \geq 2$, achieves a competitive ratio of $\min\{ (1 + \frac{1}{\gamma})(1 + \frac{k_h}{\mathrm{opt}}), \gamma\}$.
	Furthermore, if $\gamma = 2$, then the competitive ratio is $\min\{1.5 + k_h/\mathrm{opt}, 2\}$.
\end{restatable}

The more adaptive and dynamic nature of the MST problem complicates the handling of Phase $2$.
We therefore employ again a more adaptive strategy to cover for potential prediction errors in Phase $2$.
By using a charging/counting scheme that builds on K\"onig-Egerv\'ary's famous theorem on the duality of minimum vertex covers and maximum matchings in bipartite graphs, we achieve the {following result.}
\begin{restatable}{theorem}{MstTheoremTwo}
	\label{theorem_mst2}
	There is an algorithm for the MST problem under uncertainty with competitive ratio $\min\{ 1+ \frac{1}{\gamma} +  \left(5 + \frac{1}{\gamma}\right) \cdot \frac{k_h}{\mathrm{opt}},\, \max\{3,\gamma + \frac{1}{\mathrm{opt}}\}\}$, for any $\gamma\in\mathbb{Z}$ with $\gamma\geq 2$, {where $k_h$ is the hop distance of an instance}.
\end{restatable}

Further, we {refine}  our framework to obtain guarantees dependent on {the mandatory query distance} $k_M$ for the minimum and sorting problems. We observe that we can hope to obtain only a slightly worse consistency for the same robustness in comparison to the guarantees dependent on $k_h$ (cf.\ Theorem~\ref{theo_lb_sym_diff}). 
Based on this observation, we adjust the framework to be \enquote{less careful} in the first phase and repeatedly query $\gamma-1$ prediction mandatory elements and one additional element that forms a witness set with one of the queried prediction mandatory elements.
For sorting and minimum, we show that this adjustment with an unchanged second phase leads to the competitive ratio stated in the following theorem.
\begin{restatable}{theorem}{ThmMinAlpha}
	\label{thm:min-alpha}
	There is an algorithm for the minimum problem under uncertainty that, given an integer parameter $\gamma \geq 2$, achieves a competitive ratio of $\min\{ (1+\frac{1}{\gamma-1}) \cdot (1 + \frac{k_M}{\mathrm{opt}}), \gamma\}$.
\end{restatable}
The error-sensitivity can again be shown by charging each queried prediction mandatory element that turns out to not be mandatory and each additional query in the second phase to a distinct error in the $k_M$-metric. 
In contrast to the $k_h$-dependent error-sensitivity, only elements that are prediction mandatory based on the initially given information and that turn out not to be mandatory contribute to $k_M$.
Thus, we fix the set of prediction mandatory elements at the beginning of the algorithm and show that querying only those elements in the first phase is sufficient.
We remark that the integrality requirement in Theorem~\ref{thm:min-alpha} can be removed by randomization at the cost of a slightly worse guarantee.

 {Finally, we observe that for sorting a single set, a substantially better algorithm is possible: a $1$-consistent  $2$-robust algorithm with a competitive ratio that linearly degrades depending on the prediction error. Note that for a }
$1$-consistency, an algorithm \emph{must} follow the offline algorithm and cannot afford additional queries unless the predictions are wrong. 
To simultaneously guarantee $2$-robustness and error dependency, the algorithm has to perform queries in a very carefully selected order, both for the prediction mandatory elements in Phase 1 and the vertex cover in Phase 2.
By employing such a strategy, we achieve the following theorem.
\begin{restatable}{theorem}{sortingsingleset}
	\label{thm:sorting:singleset}
	For sorting under uncertainty for a single set, there is a polynomial-time algorithm with competitive ratio $\min\{1+k/\mathrm{opt}, 2\}$, for any error measure $k \in \{k_{\#}, k_M, k_h\}$.
\end{restatable}

\section{The minimum problem}
\label{sec:minimum}
We show how to implement our general framework for the minimum problem under uncertainty achieving best possible competitive ratios with respect to
the accuracy measures $k_{\#}$ and $k_M$. 

\subsection{Preliminaries}                 

We start by giving a characterization of (prediction) mandatory queries and witness sets. Secondly, we present a verification algorithm, i.e., an optimal offline algorithm.

\begin{restatable}{lem}{LemmaMandatoryMin}
\label{lema_mandatory_min}
An interval~$I_i$ is {\em mandatory} for the minimum problem if and only if
(a) $I_i$ is a true minimum of a set~$S$ and contains $w_j$ of another interval $I_j\in S\setminus \{I_i\}$ (in particular, 
if $I_j\subseteq I_i$), or
(b) $I_i$ is not a true minimum of a set~$S$ with $I_i \in S$ but contains the value of the true minimum of $S$. 
{\em Prediction mandatory} intervals are characterized equivalently, replacing true values by predicted values.
\end{restatable}

\begin{proof}
If~$I_i$ is a true minimum of~$S$ and contains~$w_j$ of another interval $I_j\in S$, then~$S$ cannot be solved even if we query all intervals in $S \setminus \{I_i\}$. 
If~$I_i$ is not a true minimum of a set $S$ with $I_i\in S$ and contains the true minimum value~$w^*$ of $S$, then~$S$ cannot be solved even if we query all intervals in $S \setminus \{I_i\}$, as we cannot prove that $w^* \leq w_i$.

If~$I_i$ is the true minimum of a set $S$, but $w_j \notin I_i$ for every $I_j \in S \setminus \{I_i\}$, then $S \setminus \{I_i\}$ is a feasible solution for~$S$.
If~$I_i$ is not a true minimum of a set~$S$ and does not contain the true minimum value of~$S$, then again $S \setminus \{I_i\}$ is a feasible solution for~$S$. If every set $S$ that contains $I_i$ falls into one of these two cases, then querying all intervals except $I_i$ is a feasible query set for the whole instance.
\end{proof}


	Lemma~\ref{lema_mandatory_min} does not only enable us to identify mandatory intervals given full knowledge of the true values, but also implies criteria to identify \emph{known mandatory} intervals, i.e., intervals that are known to be mandatory given only the intervals, and true values revealed by previous queries.
	We call an interval {\em leftmost} in a set~$S$ if it is an interval with minimum lower limit in~$S$.
	The following corollary follows from 
	Lemma~\ref{lema_mandatory_min} and gives a characterization of known mandatory intervals.


\begin{restatable}{coro}{CorMinLeftMandatory} \label{cor_min_left_mandatory}
If the leftmost interval~$I_l$ in a set~$S$ contains the true value of another interval in~$S$, then~$I_l$ is mandatory.
In particular, if $I_l$ is leftmost in $S$ and $I_j \subseteq I_l$ for some $I_j \in S \setminus \{I_l\}$, then $I_l$ is mandatory.
\end{restatable}
Every algorithm can query known mandatory intervals without worsening its competitive ratio.
	In addition to exploiting prediction mandatory elements, our algorithms rely on identifying witness sets of size two by using the following lemma.

\begin{lemma}[\cite{kahan91queries}]
		A set $\{I_i, I_j\} \subseteq S$ with $I_i \cap I_j \neq \emptyset$, and $I_i$ or~$I_j$ leftmost in~$S$, is a witness set.
\end{lemma}

Since following the predictions can lead to an arbitrarily bad robustness, our algorithms execute additional queries to verify that a prediction mandatory interval is indeed mandatory.
To do so, we observe that some intervals are rendered prediction mandatory by a single predicted value.
A predicted value~$\pred{w}_j$ {\em enforces} another interval~$I_i$ if $\pred{w}_j \in I_i$ and $I_i, I_j \in S$, where~$S$ is a set such that either~$I_i$ is leftmost in~$S$, or~$I_j$ is leftmost in~$S$ and~$I_i$ is leftmost in $S \setminus \{I_j\}$.
Corollary~\ref{cor_min_left_mandatory} implies that $I_i$ is mandatory if the predicted value of $I_j$ is correct.
It is then easy to see that, if $\pred{w}_j$ enforces~$I_i$, then $\{I_i, I_j\}$ is a witness set and $I_i$ is prediction mandatory; moreover, if $w_j \in I_i$ then~$I_i$ is mandatory.

We use Lemma~\ref{lema_mandatory_min} to design a verification algorithm. It follows the same two-phase structure as our general framework:
First, we query all mandatory intervals.
After that, each unsolved set~$S$ has the following configuration: The leftmost interval~$I_i$ has true value outside all other intervals in~$S$, and each other interval in~$S$ has true value outside~$I_i$.
Thus we can either query~$I_i$ or all other intervals that intersect~$I_i$ in~$S$ to solve it.
The optimum solution is to query a minimum vertex cover in the graph with a vertex for each interval and, for each unsolved set, an edge between the leftmost interval and the intervals that intersect it.
This algorithm may require exponential time, but this is not surprising as we can
show that the verification version of the minimum problem is NP-hard (a proof is given in Appendix~\ref{sec:nphard}).

\begin{theorem}
	The verification problem for the minimum problem under uncertainty is NP-hard. The above algorithm solves it with a minimum number of queries. 
\end{theorem}


\subsection{Algorithm regarding hop distance} 

We prove Theorem~\ref{thm_minimum:hop} by presenting Algorithm~\ref{ALG_min_beta} with a performance guarantee depending on the hop distance $k_h$, i.e., the competitive ratio $\min\{ (1 + \frac{1}{\gamma})(1 + \frac{k_h}{\mathrm{opt}}), \gamma\}$  for each integer parameter $\gamma \ge 2$.
This guarantee is best possible for $k_h = 0$ and for large~$k_h$ (Theorem~\ref{theo_minimum_combined_lb}).
Note that, for $\gamma = 2$, the algorithm also satisfies Theorem~\ref{thm:main1.5-2} for the minimum problem under uncertainty, since $k_{\#} = 0$ implies $k_h = 0$.
A complete proof of Theorem~\ref{thm_minimum:hop} is
in Appendix~\ref{app:minbeta}; here we only describe the algorithm and high level~arguments.

The algorithm follows the general framework of Section~\ref{sec:methods}.
	After preprocessing the instance by querying known mandatory intervals in Line~\ref{line_min_beta_kh_mandatory_first}, the algorithm implements the first framework phase in
	Lines~\ref{line_min_beta_kh_calc_predict_first} to~\ref{line_min_beta_kh_cond_loop}, while Lines~\ref{line_min_beta_kh_vc} to~\ref{line_min_beta_kh_after_vc} corresponds to the second phase.


\begin{algorithm}[tb]
  \KwIn{Intervals $I_1, \ldots, I_n$, prediction $\pred{w}_i$ for each $I_i$, and family of sets $\mathcal{S}$}
  \label{line_min_beta_start}
  \Repeat{no query was performed in this iteration \label{line_min_beta_kh_cond_loop}}{
    \lWhile{there is a known mandatory interval $I_i$}{query $I_i$ \label{line_min_beta_kh_mandatory_first}}
    $Q \leftarrow \emptyset$; \quad $P \leftarrow$ set of prediction mandatory intervals for current instance\; \label{line_min_beta_kh_calc_predict_first}
    \While{$P \neq \emptyset$ \KwAnd $|Q| < \gamma - 2$}{
      pick and query some $I_j \in P$; \quad $Q \leftarrow Q \cup \{I_j\}$\; \label{line_min_beta_kh_predict}
      \lWhile{there is a known mandatory interval $I_i$}{query $I_i$ \label{line_min_beta_kh_mandatory_loop}}
      $P \leftarrow$ set of prediction mandatory intervals for current instance\; \label{line_min_beta_kh_calc_predict_second}
    }
    \uIf{$\exists \mbox{ distinct } I_i,I_j,I_l$ such that $\pred{w}_j$ enforces $I_i$ and $\{I_j,I_l\}$ is a witness set \label{lin_min_beta_cond_trio}} {
      query $I_j, I_l$\; \label{line_min_beta_wit_trio}
      \lIf{$w_j \in I_i$}{query $I_i$ \label{line_min_beta_mand_trio}}
    } \lElseIf{$\exists I_i,I_j$ such that $\pred{w}_j$ enforces $I_i$ \label{line_min_beta_pair}} {
      query $I_i$ \label{line_min_beta_query_first}
    }
  }
  \lWhile{there is a known mandatory interval $I_i$}{query $I_i$ \label{line_min_beta_kh_before_vc}}
  compute and query a minimum vertex cover~$Q'$ on the current dependency graph\; \label{line_min_beta_kh_vc}
  \lWhile{there is a known mandatory interval $I_i$}{query $I_i$ \label{line_min_beta_kh_after_vc}}
  \caption{Algorithm for the minimum problem under uncertainty w.r.t.\ hop distance $k_h$}
  \label{ALG_min_beta}
\end{algorithm}



The if-statement in Lines~\ref{lin_min_beta_cond_trio} to~\ref{line_min_beta_query_first}, corresponds to the identification of three elements such that, assuming correct predictions, at least two of them are mandatory (cf. paragraph on the general framework in Section~\ref{sec:methods}).
In these lines, the algorithm first tries to identify three distinct intervals $I_i, I_j, I_l$, such that $\pred{w}_j$ enforces $I_i$ and $\{I_j, I_l\}$ is a witness set.
If there is such trio, we query $\{I_j, I_l\}$, and only query~$I_i$ if the prediction that $\pred{w}_j \in I_i$ is correct.
If the prediction is correct, then we have a set of size 3 with at least 2 mandatory intervals; otherwise we only query a witness pair, so we can enforce robustness, and if one interval in this pair is not in $\mathrm{OPT}$ then we can charge this error to the hop distance, since the prediction $\pred{w}_j$ is incorrect.
If there is no such trio, then we try to find a witness pair $\{I_i, I_j\}$ such that $\pred{w}_j$ enforces $I_i$, but initially we only query~$I_i$.
If the prediction $\pred{w}_j$ is correct, then we are querying a mandatory interval.
Otherwise, we show that $I_j$ is either queried in Line~\ref{line_min_beta_kh_mandatory_first} in the next iteration of the loop (so it is a mandatory interval), or is never queried by the algorithm; either way, the fact that this is a witness pair is enough to guarantee robustness, and if $I_i$ is not in $\mathrm{OPT}$ then we can charge this error to the hop distance.
Summing up, for each iteration of the loop we can identify a witness set of size at most~$3$, such that at least a $\frac{2}{3}$ fraction of its elements are prediction mandatory, and those that are not mandatory can be charged to the hop distance. 
For $\gamma = 2$ this concludes the description of the first framework phase.

In case of $\gamma > 2$, the algorithm follows the framework for achieving parameterized guarantees by additionally querying $\gamma -2$  prediction mandatory intervals in Lines~\ref{line_min_beta_kh_calc_predict_first} to~\ref{line_min_beta_kh_calc_predict_second}.
Doing this, each iteration of the loop identifies a witness set of size at most~$\gamma$, excluding the mandatory elements that are potentially queried in Line~\ref{line_min_beta_kh_mandatory_loop} or~\ref{line_min_beta_mand_trio}.
This ensures the robustness.
By adding the prediction mandatory elements, the local consistency (of the queries in a single iteration) improves to $\frac{\gamma+1}{\gamma}$.
All prediction mandatory elements that are not mandatory can be charged to the hop distance.

We may have an iteration of the loop in that we do not query any intervals in Lines~\ref{line_min_beta_wit_trio} and~\ref{line_min_beta_query_first}, but we show that this occurs at most once: If we cannot satisfy the conditions of Lines~\ref{lin_min_beta_cond_trio} and~\ref{line_min_beta_pair}, then there are no more prediction mandatory intervals.
After that, the algorithm will proceed to the second phase of the framework, querying a minimum vertex cover and intervals that become known mandatory.
Here we combine the at most $\gamma-2$ intervals queried in the iteration described with the intervals queried in the second phase, and it is not hard to prove $\gamma$-robustness and that every interval that is not in $\mathrm{OPT}$ can be charged to the hop distance.

\subsection{Algorithm regarding mandatory-query distance}

Now we consider the mandatory-query distance $k_M$ as measure for the prediction accuracy. We prove Theorem~\ref{thm:min-alpha} by presenting Algorithm~\ref{ALG_min_alpha} with a competitive ratio of  $\min\{ (1 + \frac{1}{\gamma-1})(1 + \frac{k_M}{\mathrm{opt}}), \gamma\}$,  for each integer parameter $\gamma \ge 2$.
This upper bound is tight for $k_M = 0$ and large~$k_M$ (Theorem~\ref{theo_lb_sym_diff}). The theorem can be generalized for arbitrary real $\gamma \geq 2$ with a marginally increased competitive ratio; see Appendix~\ref{app:min_alpha}. 
The full proof of Theorem~\ref{thm:min-alpha} appears also in Appendix~\ref{app:min_alpha}; here we outline algorithm and crucial arguments.

Algorithm~\ref{ALG_min_alpha} implements the first framework phase in Lines~\ref{line_min_param_cond} to~\ref{line_min_param_small} and afterwards executes the second phase.
To start the first phase, the algorithm computes the set~$P$ of initial prediction mandatory intervals (Lemma~\ref{lema_mandatory_min}).
Then it tries to find an interval $p \in P$ that is part of a witness set $\{p, b\}$.
If~$|P|\ge\gamma-1$, we query a set $P' \subseteq P$ of size $\gamma-1$ that includes~$p$, plus~$b$ (we allow $b \in P'$).
This is clearly a witness set of size at most $\gamma$, at least a $\frac{\gamma-1}{\gamma}$ fraction of the intervals are in~$P$, and every interval in $P \setminus \mathrm{OPT}$ is in $\mathcal{I}_P \setminus \mathcal{I}_R$.
We then repeatedly query known mandatory intervals, remove the queried intervals from~$P$ and repeat the process without recomputing~$P$, until~$P$ is empty or no interval in~$P$ is part of a witness set.

We may have one last iteration of the loop where $|P| < \gamma -1$.
After that, the algorithm will proceed to the second phase of the framework, querying a minimum vertex cover and intervals that become known mandatory.
Here we combine the at most $\gamma-2$ intervals in $P$ with the intervals queried in the second phase, and it is not hard to prove $\gamma$-robustness, and that the number of those queries can be bounded by the number of intervals in $\mathrm{OPT}$ for the current instance plus the number of intervals that are in $\mathcal{I}_P \setminus \mathcal{I}_R$ or in $\mathcal{I}_R \setminus \mathcal{I}_P$.

Note that this algorithm only uses the initial set of prediction mandatory intervals, and otherwise ignores the predicted values.
Predicting the set of prediction mandatory intervals is sufficient to execute the algorithm.

\begin{algorithm}[tb]
  \KwIn{Intervals $I_1,\ldots,I_n$, predicted value $\overline{w}_i$ for each $I_i$, family of sets $\mathcal{S}$, and parameter $\gamma$}

  $P \leftarrow$ set of initial prediction mandatory intervals (characterized in Lemma~\ref{lema_mandatory_min})\;
  \While{$\exists p \in P$ and an unqueried interval $b$ where $\{p, b\}$ is a witness set \label{line_min_param_cond}}{
    \uIf{$|P| \geq \gamma-1$ \label{line_min_param_size}}{
      pick $P' \subseteq P$ with $p \in P'$ and $|P'| = \gamma-1$\;
      query $P' \cup \{b\}$, $P \leftarrow P \setminus (P' \cup \{b\})$\; \label{line_min_param_big}
     \lWhile{there is a known mandatory interval~$I_i$}{query $I_i$, $P \leftarrow P \setminus \{I_i\}$ \label{line_min_param_mandatory}}
    } \lElse{query $P$, $P \leftarrow \emptyset$ \label{line_min_param_small}}
  }
  \lWhile{there is a known mandatory interval~$I_i$}{query $I_i$ \label{line_min_param_before_vc}}
  query a minimum vertex cover~$Q$ for the current instance \label{line_min_param_vc}\;
  \lWhile{there is a known mandatory interval~$I_i$}{query $I_i$ \label{line_min_param_mand_after_vc}}
  \caption{Algorithm for the minimum problem under uncertainty w.r.t.\ error measure $k_M$}
  \label{ALG_min_alpha}
\end{algorithm}

\section{The minimum spanning tree problem}
\label{sec:mst}
In this section, we show how the framework of Section~\ref{sec:methods} can be implemented to achieve an algorithm for the MST problem with a hop-distance dependent performance guarantee. We prove  Theorem~\ref{theorem_mst2}, which states a  competitive ratio of $\min\{ 1+ \frac{1}{\gamma} +  (5 + \frac{1}{\gamma}) \cdot \frac{k_h}{\mathrm{opt}}, \max\{3,\gamma + \frac{1}{\mathrm{opt}}\}\}$, for each integer $\gamma \ge 2$. Further, we introduce a second algorithm that achieves a better robustness at the cost of not providing an error-sensitive guarantee. More precisely, it is $1.5$-consistent and $2$-robust, which proves the MST related part of Theorem~\ref{thm:main1.5-2}. Both algorithms
use the same first phase to obtain a prediction mandatory free instance  and differ only in the second phase. We present our  implementations of the two phases in Sections~\ref{subsec_mst_phase_1} and~\ref{subsec_mst_phase_2}. 
Full proofs are given in Appendix~\ref{appx:mst}.

Our algorithms build on structural insights and characterizations of mandatory queries given in~\cite{megow17mst}, which we summarize here.
Let the \emph{lower limit tree} $T_L \subseteq E$ be an MST for
{values} $w^L$ with $w^L_e = L_e + \epsilon$ for an infinitesimally small $\epsilon > 0$. 
Analogously, let the \emph{upper limit tree} $T_U$ be an MST for {values}  $w^U$ with $w^U_e = U_e - \epsilon$. It has been shown in~\cite{megow17mst} that any non-trivial edge in $T_L \setminus T_U$ is part of any feasible query set, {i.e., it is mandatory}. {Thus, we may repeatedly query edges in
$T_L \setminus T_U$ until $T_L = T_U$ and this will not worsen the robustness or consistency. By this preprocessing, we may assume~$T_L=T_U$.
Further, we can extend the preprocessing to achieve uniqueness for $T_L$ and $T_U$.
\begin{restatable}{lemma}{LemMSTPreprocessing}
	\label{mst_preprocessing}
	By querying only mandatory elements we can obtain an instance with $T_L = T_U$ such that $T_L$ and $T_U$ are the unique lower limit tree and upper limit tree, respectively. 
\end{restatable}

Consider $T_L$ and
$f_1,\ldots,f_l$ in $E \setminus T_L$ ordered by increasing lower limits. 
For each~$i \in \{1,\ldots,l\}$, let $C_i$ be the unique cycle in $T_L \cup \{f_i\}$. 
For each $e \in T_L$ let $X_e$ be the set of edges in the cut of $G$ defined by the two connected components of $T_L \setminus \{e\}$.
We say an instance is \emph{prediction mandatory free} if it contains no prediction mandatory elements.
Otherwise, we say that the instance is \emph{non-prediction mandatory free.}
The following lemma further characterizes prediction mandatory free instances. Figure~\ref{Ex_mst_phase1_cases}(a) illustrates it.

\begin{restatable}{lemma}{LemMSTPredFreeIff}
	\label{mst_pred_free_characterization}
	{
		An instance $G$ is prediction mandatory free if and only if 
		$\pred{w}_{f_i} \ge U_{e}$ and $\pred{w}_e \le L_{f_i}$ holds for each $e \in C_i \setminus \{f_i\}$ and each cycle $C_i$ with ${i} \in \{1,\ldots,l\}$.}
\end{restatable}

\subsection{Identifying witness sets}
\label{subsec_mst_witness sets}

Before we describe our algorithms in the following sections, we introduce some preliminaries.
As already stated, the first phase of our algorithm handles non-prediction mandatory free instances until they become prediction mandatory free.
In order to achieve this goal while maintaining the desired performance guarantees, the algorithms rely on identifying witness sets on non-prediction mandatory free cycles $C_i$.

Existing algorithms for MST under uncertainty~\cite{erlebach08steiner_uncertainty,megow17mst} essentially follow the algorithms of Kruskal or Prim, and only identify witness sets in the cycle or cut that is currently under consideration.
For a given instance this corresponds to the cycle $C_1$ or the cut $X_{l_1}$, where $l_1$ is the edge with the largest upper limit in~$T_L$.
Regarding Phase $1$ of our algorithm, it might hold for the first non-prediction mandatory free cycle $C_i$ that $C_i \not= C_1$.
Since additionally $C_i \cap X_{l_1} = \emptyset$ might hold, existing methods for identifying witness sets are not sufficient for our purpose.
We show the following new structural insights that are crucial for our algorithms.

\begin{restatable}{lemma}{LemMstWitnessFir}
	\label{lemma_mst_witness_set_1}		
	Consider cycle $C_i$ with $i \in \{1,\ldots,l\}$. 
	Let $l_i \in C_i \setminus\{f_i\}$ such that $I_{l_i} \cap I_{f_i} \not= \emptyset$ and $l_i$ has the largest upper limit in $C_i \setminus \{f_i\}$, then $\{f_i,l_i\}$ is a witness set. 
	Further, if $w_{f_i} \in I_{l_i}$, then $\{l_i\}$ is a witness set.
\end{restatable}
\begin{restatable}{lemma}{LemMstWitnessSec}
	\label{lemma_mst_witness_set_2}
	Let $l_i \in C_i \setminus \{f_i\}$ with $I_{l_i} \cap I_{f_i} \not= \emptyset$ such that $l_i \not\in C_j$ for all $j < i$, then $\{l_i,f_i\}$ is a witness set.
	Furthermore, if $w_{l_i} \in I_{f_i}$, then $\{f_i\}$ is a witness set.
\end{restatable}


\subsection{Handling non-prediction mandatory free instances}
\label{subsec_mst_phase_1}

\begin{algorithm}[t]
	\KwIn{Uncertainty graph $G=(V,E)$ and predictions $\pred{w}_e$ for each {$e \in E$}}
	{Sequentially query prediction mandatory elements while ensuring unique $T_L = T_U$ until either $\gamma - 2$ prediction mandatory elements are queried or the instance is prediction mandatory free\label{line_mst_one_fillup}}\;
	Let $T_L$ be the lower limit tree and $f_1,\ldots,f_l$ be the edges in $E \setminus T_L$ ordered by lower limit non-decreasingly\label{line_mst_one_order}\;
	\ForEach{{$C_i$ with $i=1$ to $l$\label{line_mst_one_foreach_f}\label{line_mst_ine_unique_cycle}}}{
		\lIf{$C_i$ is not prediction mandatory free\label{line_mst_one_if_pred_free}}{
			{Apply Lemma~\ref{mst_phase1_case_a},~\ref{mst_phase1_case_b} or~\ref{mst_phase1_case_c}\label{line_mst_one_lemma_queries} and restart\label{line_mst_one_restart}}
		}
	}	
	\caption{Phase $1$ of the algorithms for MST under uncertainty}
	\label{ALG_mst_part_1}
\end{algorithm}


Algorithm~\ref{ALG_mst_part_1} implements Phase $1$ of our algorithms. 
In each iteration the algorithm starts by querying elements that are prediction mandatory for the current instance.
The set of prediction mandatory elements can be computed using the verification algorithm~\cite{erlebach14mstverification}.
Our algorithm sequentially queries such elements until either $\gamma - 2$ prediction mandatory elements have been queried or no more exist. 
After each query, the algorithm ensures unique $T_L = T_U$ by using Lemma~\ref{mst_preprocessing}.
Note that the set of prediction mandatory elements with respect to the current instance can change when elements are queried, and therefore we query the elements sequentially.
We can prove that each of the {at most} $\gamma-2$ elements is either mandatory or contributes one to the hop distance $k_h$.

Then, the algorithm iterates through $i \in \{1,\ldots,l\}$ and stops if the current cycle $C_i$ is non-prediction mandatory free. 
If it finds such a cycle, it queries edges on the cycle and possibly future cycles and restarts. 
The algorithm terminates when all $C_i$ are prediction mandatory free 
that is {at the latest when} all edges in $E$ have been queried. 
When the algorithm finds a non-prediction mandatory free cycle $C_i$, it carefully selects edges to query such that the following statements hold: 

\begin{compactenum}
	\item The algorithm only queries witness sets of size {one or} two, and sets of size three such that at least two elements are part of any feasible query set.

	\item If the algorithm queries a witness set {$W=\{e_1,e_2\}$} of size two, then either {$W \subseteq Q$} for each feasible query set $Q$ or the hop distances of $e_1$ and $e_2$ satisfy $h_{e_1} + h_{e_2} \ge 1$.

	\item In an only exception, the algorithm queries single elements $e$ that form witness sets $\{e,f(e)\}$ with distinct elements $f(e)$, 
	and the algorithm \emph{guarantees} that $f(e)$ remains unqueried during the complete execution.
	Since $\mathrm{OPT}$ must query at least one element of $\{e,f(e)\}$ and we guarantee that the algorithm queries exactly one element, querying such elements does not hurt the robustness or consistency as long as each such queried $e$ can be matched with a distinct $f(e)$.
	
	Let $E$ be the set of such queried edges.
	For the sake of our analysis, we assume without loss of generality that $E \subseteq \mathrm{OPT}$ and treat each $e \in E$ as a witness set of size one.
	We can do this without loss of generality since if $e \not\in \mathrm{OPT}$ we know $f(e) \in \mathrm{OPT}$ and can charge $e$ against $f(e)$.
\end{compactenum}
Ignoring the last iteration where the instance becomes prediction mandatory free and
{possibly less than} $\gamma-2$ prediction mandatory elements are queried, the algorithm  queries in each iteration~$\gamma - 2$ prediction mandatory elements and a set {$W$} that satisfies 
the three statements. This implies the following lemma.

\begin{restatable}{lem}{MSTEndOfPhaseOne}
	\label{mst_end_of_phase_one}
	After executing Algorithm~\ref{ALG_mst_part_1} the instance is prediction mandatory free and, ignoring the last iteration {of Line~\ref{line_mst_one_fillup}}, $|\mathrm{ALG}| \le \min\{ (1 + \frac{1}{\gamma}) \cdot (|\mathrm{ALG} \cap \mathrm{OPT}| + k_h), \gamma \cdot |\mathrm{ALG} \cap \mathrm{OPT}|\}$ holds for the set of edges $\mathrm{ALG}$ queried by Algorithm~\ref{ALG_mst_part_1} and any optimal solution $\mathrm{OPT}$.
\end{restatable}

In the last iteration, a (possibly empty) set $P$ of at most $\gamma-2$ prediction mandatory elements is queried.
Lemma~\ref{mst_pred_free_characterization} implies that only the last execution of Line~\ref{line_mst_one_fillup} might query less than $\gamma-2$ prediction mandatory elements.
As {each $e \in P$ is} either mandatory or contributes one to the hop distance,
querying $P$ does not violate the consistency.
{For $\gamma > 2$, we ensure the $(\gamma+\frac{1}{\mathrm{opt}})$-robustness by charging $P$ against the queries of the $3$-robust Phase $2$ of the algorithm.
Charging the first $\gamma-3$ elements of $P$ against the $3$-robust Phase $2$ leads to $\gamma$-robustness while the final element of $P$ leads to the additive term $\frac{1}{\mathrm{opt}}$.

The following
lemmas give algorithmic actions with a guarantee that the three statements are fulfilled. Each of them considers a cycle $C_i$ such that all $C_j$ with $j < i$ are prediction mandatory free, $l_i$ is the edge with the highest upper limit in $C_i \setminus \{f_i\}$ and predictions are as indicated in Figure~\ref{Ex_mst_phase1_cases}~b)-d).
The proofs of the three lemmas rely on the structural insights of Subsection~\ref{subsec_mst_witness sets}.


\begin{restatable}{lem}{MstPhaseOneCaseA}
	\label{mst_phase1_case_a}
	If $\pred{w}_{f_i} \in I_{l_i}$ and $\pred{w}_{l_i} \in I_{{f_i}}$, then querying $\{f_i,l_i\}$ satisfies the three statements.
\end{restatable}
\begin{restatable}{lem}{MstPhaseOneCaseB}
	\label{mst_phase1_case_b}
	
	Assume $\w_{f_i} \in I_{l_i}$ but $\w_{l_i} \not\in I_{f_i}$.
	Let $l_i'$ be the edge with the highest upper limit in $C_i \setminus \{f_i,l_i\}$ and  $I_{l_i'} \cap I_{f_i} \not= \emptyset$. 
	If no $l_i'$ exists, then querying $l_i$, and querying $f_i$ only if  $w_{l_i} \in I_{f_i}$, satisfies the three statements. 
	If $l_i'$ exists, then querying $\{f_i,l_i\}$, and querying $l_i'$  only if $w_{f_i} \in I_{l_i}$ and $w_{l_i} \not\in I_{f_j}$ for each $j$ with $l_i \in C_j$, satisfies the three statements.
\end{restatable}
\begin{restatable}{lem}{MstPhaseOneCaseC}
	\label{mst_phase1_case_c}
	Assume $\w_{l_i'} \in I_{f_i}$ for some $l_i' \in C_i\setminus\{f_i\}$ but $\w_{f_i} \not\in I_{l_i}$. Let $f_j$ be the edge with the smallest lower limit in $X_{l_i'} \setminus \{l_i',f_i\}$ and $I_{f_j}\cap I_{l_i'}\not=\emptyset$.
	If $f_j$ does not exist, then querying $f_i$, and querying $l_i'$ only if $w_{f_i} \in I_{l_i'}$, satisfies the three statements. 
	If $f_j$ exists, querying $\{f_i,l_i'\}$, and also querying $f_j$ only if $w_{l_i'}\in I_{f_i}$ and $w_{f_i} \not\in I_{e}$ for each $e \in C_i$, satisfies the three statements.
	
\end{restatable}

 
 \begin{figure}[th]
		\begin{minipage}{0.24\textwidth}
		\centering
        \begin{tikzpicture}[line width = 0.3mm, scale = 0.8, transform shape]
        \intervalp{$I_{f_i}$}{-3}{-0.5}{0}{-0.7}
        \intervalp{$I_{l_i}$}{-3.5}{-1}{0.5}{-3.3}
        \intervalp{}{-4}{-1.5}{1}{-3.2}
		\path (-2.75, 1.6) -- (-2.75, 1.6) node[font=\LARGE, midway, sloped]{$\dots$};
		\node[] at (-4.75,1.8){$(a)$};
		\end{tikzpicture}
	\end{minipage}
	\begin{minipage}{0.24\textwidth}
		\centering
		\begin{tikzpicture}[line width = 0.3mm, scale = 0.8, transform shape]
		\intervalp{$I_{f_i}$}{-3}{-0.5}{0}{-2.5}
		\intervalp{$I_{l_i}$}{-3.5}{-1}{0.5}{-2.8}
		\interval{}{-4}{-1.5}{1}
		\path (-2.75, 1.6) -- (-2.75, 1.6) node[font=\LARGE, midway, sloped]{$\dots$};
		\node[] at (-4.75,1.8){$(b)$};
		\end{tikzpicture}
	\end{minipage}
	\begin{minipage}{0.24\textwidth}
		\centering
		\begin{tikzpicture}[line width = 0.3mm, scale = 0.8, transform shape]
		\intervalp{$I_{f_i}$}{-3}{-0.5}{0}{-2.5}
		\intervalp{$I_{l_i}$}{-3.5}{-1}{0.5}{-3.3}
		\interval{}{-4}{-1.5}{1}
		\path (-2.75, 1.6) -- (-2.75, 1.6) node[font=\LARGE, midway, sloped]{$\dots$};
		\node[] at (-4.75,1.8){$(c)$};
		\end{tikzpicture}
	\end{minipage}
	\begin{minipage}{0.24\textwidth}
		\centering
		\begin{tikzpicture}[line width = 0.3mm, scale = 0.8, transform shape]
		\intervalp{$I_{f_i}$}{-3}{-0.5}{0}{-0.7}
		\interval{}{-3.5}{-1}{0.5}
		\intervalp{$I_{l_i'}$}{-4}{-1.5}{1}{-1.75}
		\path (-2.75, 1.6) -- (-2.75, 1.6) node[font=\LARGE, midway, sloped]{$\dots$};
		\node[] at (-4.75,1.8){$(d)$};
		\end{tikzpicture}
	\end{minipage}
	\caption{Intervals with predictions indicated as red crosses. {$a)$ Prediction mandatory free cycle. Illustration of the situations in the Lemmas~\ref{mst_phase1_case_a} $(b)$, \ref{mst_phase1_case_b} $(c)$ and~\ref{mst_phase1_case_c} $(d)$.}} 
	\label{Ex_mst_phase1_cases}
\end{figure}


\subsection{Handling prediction mandatory free instances}
\label{subsec_mst_phase_2}

This section describes Phase 2 of our algorithms. For prediction mandatory free instances, we present Algorithm~\ref{ALG_mst_part_2} with \emph{recovery strategies} A and B (in Line~\ref{line_mst_two_recovery}) that lead to the guarantees of Lemma~\ref{mst_end_of_phase_2}.  
Our full algorithms execute Phase $1$ followed by Phase $2$ and differ only in the recovery strategy. 
Using the introduced ideas and lemmas, we can {prove}
the MST part of Theorem~\ref{thm:main1.5-2} (recovery A) and Theorem~\ref{theorem_mst2}~(recovery~B).

\begin{restatable}{lem}{MSTEndOfPhaseTwo}
	\label{mst_end_of_phase_2}
	If Algorithm~\ref{ALG_mst_part_2} is executed on a prediction mandatory free instance, then in each iteration the instance remains prediction mandatory free. Furthermore, recovery strategy A guarantees {$1$-consistency} and $2$-robustness and recovery strategy B guarantees $|\mathrm{ALG}| \le \min\{\mathrm{opt} + {5}\cdot k_h, 3\cdot \mathrm{opt}\}$.
\end{restatable}

Assume again unique $T_L = T_U$. In a prediction mandatory free instance $G=(V,E)$, each $f_i \in E \setminus T_L$ is predicted to be maximal on cycle $C_i$, and each $l \in T_L$ is predicted to be minimal in $X_l$. 
{If these predictions are correct, then the optimal query set is a minimum vertex cover in a bipartite graph $\bar{G} = (\bar{V},\bar{E})$ with $\bar{V} = E$ (excluding trivial edges) and $\bar{E} = \{ \{f_i,e\} \mid i \in \{1,\ldots,l\}, e \in C_i \setminus \{f_i\} \text{ and } I_e \cap I_{f_i} \not= \emptyset\}$ \cite{erlebach14mstverification,megow17mst}. We refer to $\bar{G}$ as the {\em vertex cover instance}.}
Note that {if a query reveals that} an $f_i$ is not maximal on $C_i$ or an $l_i$ is not minimal in $X_{l_i}$, then the vertex cover instance changes.
Because of this and in contrast to the minimum problem, non-adaptively querying $VC$ can lead to a competitiveness worse than $2$.

Let $VC$ be a minimum vertex cover of $\bar{G}$.
The idea of the algorithm is to sequentially query each $e \in VC$ and charge for querying $e$ by a distinct non-queried element $h(e)$ such that $\{e,h(e)\}$ is a witness set.
Querying exactly one element per
distinct witness set implies optimality.
To identify~$h(e)$ for each element $e \in VC$, we use the fact that
K\"onig's Theorem (e.g,~\cite{Biggs1986}) and the duality between minimum vertex covers and maximum matchings in bipartite graphs imply that there is a matching $h$ that maps each $e \in VC$ to a distinct $e' \not\in VC$. 
While the sets $\{e,h(e)\}$ with $e \in VC$ in general are not witness sets, querying $VC$ in a specific order until the vertex cover instance changes guarantees that $\{e,h(e)\}$ is a witness set for each already queried~$e$.  

\begin{restatable}{lem}{MstPhaseTwoOne}
	\label{mst_phase2_1}
	Let $f'_1,\ldots,f'_g$ be the edges in $VC \setminus T_L$ ordered by lower limit non-decreasingly and let $l'_1,\ldots,l'_k$ be the edges in $VC \cap T_L$ ordered by upper limit non-increasingly. 
	Let $b$ be such that each $f'_{i}$ with $i < b$ is maximal in cycle $C_{f'_i}$, then $\{f'_{i},h(f'_{i})\}$ is a witness set for each $i \le b$.
	Let $d$ be such that each $l'_{i}$ with $i < d$ is minimal in cut $X_{l'_i}$, then $\{l'_{i},h(l'_{i})\}$ is a witness set for each $i \le d$.
\end{restatable}

\begin{algorithm}[tb]
	\KwIn{Prediction mandatory free graph $G=(V,E)$ and predictions $\pred{w}_e$ for each {$e \in E$}}
	Compute maximum matching $h$ and minimum vertex cover $VC$ for $\bar{G}$ and initialize $W = \emptyset$\label{line_mst_two_compute_vc}\;
	Let $f'_1,\ldots,f'_g$ and $l'_1,\ldots,l'_k$ be as described in Lemma~\ref{mst_phase2_1}\label{line_mst_two_l_edges}\;
	\For{$e$ chosen sequentially from the {ordered list} $f'_1,\ldots,f'_g,l'_1,\ldots,l'_k$\label{line_mst_two_main_for}}{
		Query $e$, and ensure unique $T_L = T_U$\label{line_mst_two_query_vc}\; 
		If $\{e,h(e)\} \cap W = \emptyset$, add $h(e)$ to $W$. Otherwise query $h(e)$ {and ensure unique $T_L=T_U$}\label{line_mst_two_ensure_three_robust}\;
		If the vertex cover instance changed, execute a recovery strategy and restart at Line $2$\label{line_mst_two_recovery}\label{line_mst_two_restart_if}\;
	}
	\caption{Phase $2$ of the algorithms for MST under uncertainty}
	\label{ALG_mst_part_2}
\end{algorithm}

Algorithm~\ref{ALG_mst_part_2} queries $VC$ in the order $f'_1,\ldots,f'_g,l'_1,\ldots,l'_k$ (Lemma~\ref{mst_phase2_1}) until the vertex cover instance {$\bar{G}$} changes. 
If it does not change, $|VC|$ is a lower bound on $\mathrm{opt}$ and  the algorithm only queries $VC$ and a set $M$ of mandatory elements that were queried as elements of $T_L\setminus T_U$.
Since we can show that each $e \in M$ contributes one to $k_h$, it follows $|\mathrm{ALG}| \le \min\{\mathrm{opt} +k_h,2\cdot \mathrm{opt}\}$.

If the vertex cover instance changes, Line~\ref{line_mst_two_recovery} executes a recovery strategy and restarts.
The challenge here is that, after restarting, an element $h(e)$ that was used to charge for an already queried $e$ might be used again to charge for a different element $e'$.
This can happen if $h(e)$ is not queried and matched to element $e'$ after the restart. To handle this problem the algorithm uses the set $W$ to keep track of the elements $h(e)$ for already queried elements $e$ and uses them in charging schemes when executing the recovery strategies.

\medskip 
\noindent {\bf Recovery strategy A} The first recovery strategy can be used to achieve $2$-robustness and show the MST part of Theorem~\ref{thm:main1.5-2}.
It queries before a restart the set $W$ of non-queried elements that were used to charge for already queried elements, ensures unique $T_L=T_U$ and restarts with re-computed $VC$ and $h$. Since each $h(e) \in W$ forms a witness set with a distinct $e$ (Lemma~\ref{mst_phase2_1}), this strategy ensures~$2$-robustness.

\medskip
\noindent {\bf Recovery strategy B} This strategy can be used to achieve the error-sensitive guarantee $|\mathrm{ALG}| \le \min\{\mathrm{opt} + {5} \cdot k_h, 3 \cdot \mathrm{opt}\}$.
In this case querying $W$ to ensure $2$-robustness might violate $|\mathrm{ALG}| \le \mathrm{opt} + {5} \cdot k_h$. 
Instead of preventing that an element $h(e)$ is used to charge for a second element, the algorithm prevents $h(e)$ from being used to charge for three elements.
To achieve this, Line~\ref{line_mst_two_ensure_three_robust} queries $h(e)$ when it is used to charge for a second element $e'$. 
As $U = \{h(e),e,e'\}$ is a witness set, this ensures $3$-robustness. Furthermore, two elements of $U$ might not be part of an optimal solution. However, executing the Otherwise-part of Line~\ref{line_mst_two_ensure_three_robust} at most $2 \cdot k_h$ times ensures $|\mathrm{ALG}| \le \mathrm{opt} + {5} \cdot k_h$.
Note that the factor is $5$ instead of $4$ because the errors used to bound the number of executions of the Otherwise-part of Line~\ref{line_mst_two_ensure_three_robust} and the errors used to charge for the queried elements of $T_L \setminus T_U$ in Lines~\ref{line_mst_two_query_vc} and~\ref{line_mst_two_ensure_three_robust} are not necessarily disjoint.
This uses Lemma~\ref{mst_phase2_2} and a restart with a specific matching $h'$ that does not contain too many non-queried elements of $W$. 

\begin{restatable}{lem}{MstPhaseTwoTwo}
	\label{mst_phase2_2}
	Let $\bar{G}'= (\bar{V}',\bar{E}')$ be the changed vertex cover instance of Line~\ref{line_mst_two_recovery}, then $\overline{h}=\{\{e,e'\} \in h \mid \{e,e'\} \in \bar{E}'\}$ defines a partial matching for $\bar{G'}$. Let $h'$ be the maximum matching for $\bar{G}'$ computed by completing $\bar{h}$ using
	{a standard augmenting path algorithm~\cite{AhujaMO1993book}} and let $VC'$ be the vertex cover defined by $h'$. Then restarting Algorithm~\ref{ALG_mst_part_2} with $VC=VC'$ and $h=h'$ implies that Line~\ref{line_mst_two_ensure_three_robust} queries at most $2 \cdot k_h$~times.
\end{restatable}


\section{The sorting problem}
\label{sec:sorting}
There is a simple reduction from the sorting problem under uncertainty to the minimum problem.
For each intersecting pair of intervals in the same set in the sorting problem, we construct a corresponding set in the minimum problem, consisting of only this pair.
If we have a solution for the sorting problem, then we clearly can determine the minimum interval in each pair.
Conversely, if we know the minimum interval in each pair, then we can sort the intervals accordingly.
Thus the sorting problem is a particular case of the minimum problem with sets of size 2, and all our algorithmic results for the minimum problem transfer to the sorting problem.
However, the sorting problem has a simpler characterization for mandatory intervals: any interval that contains the true value of another interval in the same set is mandatory~\cite{halldorsson19sortingqueries}.
Still, 
we cannot hope for better guarantees for sorting due to the lower bounds in Theorems~\ref{theo_minimum_combined_lb} and~\ref{theo_lb_sym_diff}.
Moreover, the NP-hardness of the verification problem of the minimum holds for sets of size 2 and, thus, it holds  for sorting overlapping~sets. 

Nevertheless, if we are sorting a single set or disjoint sets, then there is a better algorithm than the ones presented for the minimum problem.
The algorithm  performs at most $\min\{\mathrm{opt} + k, 2 \cdot \mathrm{opt}\}$ queries, for any $k \in \{k_{\#}, k_M, k_h\}$, and thus satisfies Theorem~\ref{thm:sorting:singleset} and is optimal due to Theorem~\ref{thm_lb_error_measure}.
The main fact that makes the sorting problem easier for a single set is that the intersection graph is an interval graph~\cite{lekkeikerker62interval}.
Moreover, witness sets are not influenced by other intervals, because any two intersecting intervals constitute a witness set~\cite{halldorsson19sortingqueries}.
We give a full proof of Theorem~\ref{thm:sorting:singleset} in Appendix~\ref{app:sorting}; in the remainder of the section we present the algorithm and high level arguments on why it obtains the desired result.

To obtain a guarantee of $\mathrm{opt} + k$ for any measure~$k$, the algorithm must trust the predictions as much as possible.
In particular, our algorithm queries all prediction mandatory intervals}.
We can do this and still guarantee 2-robustness because intervals that contain the same predicted value form a clique in the initial interval graph, and in any clique at most one query can be avoided~\cite{halldorsson19sortingqueries}.
However, in the second phase of the framework, when there are no more prediction mandatory intervals and we query a minimum vertex cover and intervals that become known mandatory, we may have different minimum vertex covers, so in order to maintain 2-robustness we must be more careful.
We show that each component of the intersection graph at this point must be a path.
The more intricate case is when we have an even path~$P$, because we have two minimum vertex covers; we devise a charging scheme to decide which of them we query.
This scheme is based on a forest of arborescences that is built according to the relation between prediction mandatory intervals and predicted values, which we define more precisely in the next paragraph.
This forest is then used to partition the prediction mandatory intervals into sets that correspond to cliques in the initial interval graph, in such a way that only roots or children of the roots can be isolated in this clique partition.
(When a root is isolated, we show that we can build a different clique partition for that component without isolated intervals.)
We then show that only the endpoints of~$P$ can be part of this forest of arborescences.
Thus~$P$ along with the isolated vertices in the clique partition that are children of the endpoints of~$P$ constitute an induced subgraph of size at most $|P|+2$.
If the size is $|P| + 1$, then we have to ensure that we query the vertex cover that contains the endpoint that is a parent of an isolated vertex in the clique partition; otherwise we can choose an arbitrary vertex cover.
On the other hand, if we have an odd path, then it has a single minimum vertex cover, and we show that this is always a good choice.

\begin{algorithm}[tb]
\KwIn{Ground set of intervals~$\mathcal{I} = \{I_1, \ldots, I_n\}$, and predictions $\pred{w}_1, \ldots, \pred{w}_n$}
  $\mathcal{E} \leftarrow \emptyset$; \quad $C_1, C_2, \ldots, C_n \leftarrow \emptyset$\;
  \KwLet $\mathcal{I}_P$ be the set of prediction mandatory intervals\label{line:computepm}\;
  \lForEach{$I_i \in \mathcal{I}_P$}{$\pi(i) \leftarrow j$ for some $j \neq i$ with $\pred{w}_j \in I_i$\label{line:findparent}}
  \lWhile{$\exists i \neq j$ with $I_j \subseteq I_i$, or~$I_j$ was queried and $w_j \in I_i$}{query $I_i$\label{line:mandatoryproper}}
  \KwLet $\mathcal{S}$ be the set of intervals in $\mathcal{I}_P$ that were not queried yet\label{line:fixS}\;
  \ForEach{$I_i \in \mathcal{S}$}{
    query $I_i$\label{line:containpredicted}\;
    \lIf{$(I_{\pi(i)}, I_i)$ does not create a cycle in $(\mathcal{I}, \mathcal{E})$}{$\mathcal{E} \leftarrow \mathcal{E} \cup \{(I_{\pi(i)}, I_i)\}$\label{line:addedge}}
  }
  \lWhile{$\exists i \neq j$ where~$I_j$ was queried and $w_j \in I_i$}{query $I_i$\label{line:mandatory}}
  \While{$\mathcal{S} \neq \emptyset$\label{line:cliquepartitionbegin}}{
    \KwLet $I_i$ be a deepest vertex in the forest of arborescences $(\mathcal{I}, \mathcal{E})$ among those in~$\mathcal{S}$\;
    \If{$(I_{\pi(i)}, I_i) \in \mathcal{E}$}{
      $C_{\pi(i)} \leftarrow \{I_{i'} \in \mathcal{S} : (I_{\pi(i)}, I_{i'}) \in \mathcal{E}\}$\;
      \lIf{$I_{\pi(i)} \in \mathcal{S}$}{$C_{\pi(i)} \leftarrow C_{\pi(i)} \cup \{I_{\pi(i)}\}$}
      $\mathcal{S} \leftarrow \mathcal{S} \setminus C_{\pi(i)}$\label{line:cliquepartitionend}\;
    }
    \lElse{$C_i \leftarrow \{I_i\}$; \quad $\mathcal{S} \leftarrow \mathcal{S} \setminus C_i$\label{line:rootisolated}}
  }  
  \While{the problem is unsolved\label{line:vcbeginsort}}{
    \KwLet $P = x_1 x_2 \cdots x_p$ be a component of the current intersection graph which is a path with $p \geq 2$\; \label{line:looppaths}
    \lIf{$p$ is odd}{query $I_{x_2}, I_{x_4}, \ldots, I_{x_{p-1}}$\label{line:pathodd}}
    \Else{
      \lIf{$|C_{x_1}| = 1$}{query $I_{x_1}, I_{x_3}, \ldots, I_{x_{p-1}}$\label{line:patheven1}}
      \lElse{query $I_{x_2}, I_{x_4}, \ldots, I_{x_p}$\label{line:patheven2}}
    }
    \lWhile{$\exists i \neq j$ where~$I_j$ was queried and $w_j \in I_i$}{query $I_i$\label{line:mandatory2}}
  }
\caption{A nicely degrading algorithm for sorting with predictions.}
\label{fig:sorting1cons2rob}
\end{algorithm}


A pseudocode is given in Algorithm~\ref{fig:sorting1cons2rob}.
The first phase of the algorithm consists of Lines~\ref{line:computepm}--\ref{line:mandatory}, in which we query known mandatory and prediction mandatory intervals.
We fix the set $\mathcal{I}_P$ of initial prediction mandatory intervals, and for each interval $I_i \in \mathcal{I}_P$ we assign a {\em parent} $\pi(i)$, meaning that $\pred{w}_{\pi(i)} \in I_i$.
Next we query known mandatory intervals to ensure that the intersection graph becomes a proper interval graph, and let $\mathcal{S}$ be the remaining intervals in $\mathcal{I}_P$.
We then query every $I_i \in \mathcal{S}$ and include in set~$\mathcal{E}$ a directed edge $(I_{\pi(i)}, I_i)$ if that does not create a cycle in the graph $(\mathcal{I}, \mathcal{E})$; this graph $(\mathcal{I}, \mathcal{E})$ is the forest of arborescences previously mentioned.
In Lines~\ref{line:cliquepartitionbegin}--\ref{line:rootisolated}, we partition~$\mathcal{S}$ into cliques of the initial interval graph.
We traverse each component of the forest from the deepest leaves towards the root, so we guarantee that only roots or children of the roots can be isolated in the final partition.
The second phase of the framework consists of Lines~\ref{line:vcbeginsort}--\ref{line:mandatory2}: We use the size of the sets in the clique partition to decide between different minimum vertex covers, and then we query intervals that become known mandatory.

It is clear that this algorithm can be implemented in polynomial time.




\section{Experimental results}
\label{sec:exp}
{We tested the practical performance of our algorithms in simulations and highlight here the results for the minimum problem.} Further results on the MST as well as details on the generation of instances and predictions are  provided in the appendix.
Our instances {were generated} by randomly drawing interval sets from interval graphs,  {obtained from re-interpreted SAT instances from the rich SATLIB library~\cite{hoos2000satlib}.}
Our instances have between~$48$ and $287$ intervals and a variable number of overlapping sets.
For each instance we generated $125$ different predictions while ensuring that the predictions cover a wide range \mbox{of relative errors $k_M/\mathrm{opt}$}.

Figure~\ref{fig_experiments} shows the results of over $230,000$ simulations (instance and predictions pairs).
The figure compares the results of our prediction-based {Algorithms~\ref{ALG_min_beta} and~\ref{ALG_min_alpha} for different choices of the parameter $\gamma$ with the standard {\em witness set algorithm}. The latter sequentially queries witness sets of size two and achieves the best possible competitive ratio of $2$ without predictions~\cite{kahan91queries}.}
The Algorithms~\ref{ALG_min_beta} and~\ref{ALG_min_alpha}, for every selected choice of $\gamma$, outperform the witness set algorithm up to a relative error of approximately $2.8$ and $1.5$, respectively.
For small values of $\gamma$, Algorithm~\ref{ALG_min_beta} outperforms the witness set algorithm even for \emph{every} relative error.
{Further, the parameter $\gamma$ reflects well the robustness-performance tradeoff for both algorithms: } a high value $\gamma$ is beneficial for accurate predictions while a low value for $\gamma$ gives robustness against very inaccurate predictions.
{In the extreme case, $\gamma = |\mathcal{I}|$,  Algorithm~\ref{ALG_min_alpha} directly follows the predictions; while it it is superior for small errors, it gets outperformed by algorithms with smaller $\gamma$ when the relative error is growing.}
The results indicate that Algorithm~\ref{ALG_min_beta} performs better than Algorithm~\ref{ALG_min_alpha}.
For both algorithms the performance gap between the different values for $\gamma$ appears less significant for small relative errors, 
which suggests that selecting $\gamma$ not too close to the maximum value $|\mathcal{I}|$ might be beneficial.
For Algorithm~\ref{ALG_min_beta} the results even suggest that selecting $\gamma = 2$ might be the most beneficial choice.
\begin{figure}[tbh]
	\centering
	
	\begin{tikzpicture}
	    \begin{groupplot}[group style={group size= 2 by 1,horizontal sep = 1.25cm}]
	    	\nextgroupplot[
					,title style={font=\tiny}
					,xlabel={$k_M / \mathrm{opt}$}
					,ylabel={Competitive ratio (mean)}
					,grid=minor
					,xmin = 0
					,ymin = 1
					,label style={font=\tiny},
					,tick label style={font=\tiny}  
					,legend entries={
									Alg.~\ref{ALG_min_beta} ($\gamma = 2$),
									Alg.~\ref{ALG_min_beta} ($\gamma = 3$),
									Alg.~\ref{ALG_min_beta} ($\gamma = 4$),
									Alg.~\ref{ALG_min_beta} ($\gamma = 8$),
									Alg.~\ref{ALG_min_beta} ($\gamma = \mathcal{I}$),
									Alg.~\ref{ALG_min_alpha} ($\gamma = 2$),
									Alg.~\ref{ALG_min_alpha} ($\gamma = 3$),									
									Alg.~\ref{ALG_min_alpha} ($\gamma = 4$),										
									Alg.~\ref{ALG_min_alpha} ($\gamma = 8$),					 					
									Alg.~\ref{ALG_min_alpha} ($\gamma = 12$),									
									Alg.~\ref{ALG_min_alpha} ($\gamma = |\mathcal{I}|$),	
									Witness Set Alg.}
					,legend style={at={(axis cs:4.9,2.1)},anchor= east, font = \tiny}
					,table/col sep=comma,
					width=10cm,
					height=5.5cm]
				\addplot[blue!60!black,mark color=white,mark=halfsquare*] table [x = Error_bin, y = PredictionOptimalAlgorithm_002_cr] {exp_results/min_error_sum.csv};
				\addplot[cyan!60!black,mark color=white,mark=halfsquare*,mark options={rotate=180}] table [x = Error_bin, y = PredictionOptimalAlgorithm_003_cr] {exp_results/min_error_sum.csv};
				\addplot[yellow!60!black,mark color=white,mark=halfsquare left*] table [x = Error_bin, y = PredictionOptimalAlgorithm_004_cr] {exp_results/min_error_sum.csv};
				\addplot[orange!60!black,mark color=white,mark=halfsquare right*] table [x = Error_bin, y = PredictionOptimalAlgorithm_008_cr] {exp_results/min_error_sum.csv};
				\addplot[red!60!black,mark color=red!60!black,mark=halfsquare right*] table [x = Error_bin, y = PredictionOptimalAlgorithm_292_cr] {exp_results/min_error_sum.csv};
					
				\addplot[blue,mark color=white,mark=halfcircle*,mark options={rotate=180}] table [x = Error_bin, y = ParameterizedAlgorithm_002_cr] {exp_results//min_error_sum.csv};	
				\addplot[cyan,mark color=white,mark=halfcircle*] table [x = Error_bin, y = ParameterizedAlgorithm_003_cr] {exp_results//min_error_sum.csv};	
				\addplot[yellow!75!black,mark color=white,mark=halfcircle*,mark options={rotate=90}] table [x = Error_bin, y = ParameterizedAlgorithm_004_cr] {exp_results/min_error_sum.csv};	
				\addplot[orange,mark color=white,mark=halfcircle*,mark options={rotate=270}] table [x = Error_bin, y = ParameterizedAlgorithm_008_cr] {exp_results/min_error_sum.csv};	
				\addplot[red,mark color=red,mark=*] table [x = Error_bin, y = ParameterizedAlgorithm_012_cr] {exp_results/min_error_sum.csv};	
	 			\addplot[purple!60!black,mark color=purple!60!black,mark=triangle*] table [x = Error_bin, y = ParameterizedAlgorithm_292_cr] {exp_results/min_error_sum.csv};	
	 			\addplot[darkgray,mark color=darkgray,mark=diamond*] table [x = Error_bin, y = WitnessSetAlgorithm_cr] {exp_results/min_error_sum.csv};
	    \end{groupplot}
		
	\end{tikzpicture}
	\caption{Experimental results for the minimum problem under uncertainty. Instances and predictions were grouped into equal size bins ($0.2$) according to their relative error $k_M/\mathrm{opt}$.}
	\label{fig_experiments}
\end{figure}




\section*{Final remarks}
In this paper we propose to use (possibly machine-learned) predictions for improving query-based algorithms when coping with explorable uncertainty. Our methods prove that untrusted predictions allow for rigorous worst-case guarantees that {overcome} known lower bounds. We also discuss different measures for the inaccuracy of predictions, which might be of independent interest, and for which we show the learnability of predictions with small error.
By providing trustable guarantees, we contribute to the challenge of building trustable AI systems and the applicability also for safety-critical applications where such guarantees are obligatory. 
It would be interesting to study the power of predictions for other (theoretically interesting and practically relevant) problems and, possibly, for other predictor models. {We also hope to foster research on explorable uncertainty with untrusted predictions for other natural (optimization) problems.} 

While we ask, in our work, for the minimum number of queries to solve a problem {\em exactly}, it would be natural to ask for approximate solutions. The bad news is that for all problems considered here, there is no improvement over the robustness guarantee of $2$ possible even when allowing an arbitrarily large approximation of the exact solution. This follows directly from a lower bound example with two uncertain elements used in the context of finding MSTs in~\cite[Section 10]{megow17mst}. However, it remains open whether an improved consistency resp. error-dependent competitive ratio is possible.

In contrast to our adversarial model, one may assume that the realization of an uncertain value is drawn randomly according to some known distribution. Improved results are possible {\em in expectation}, as has been shown for sorting~\cite{ChaplickHLT20} and the minimum problem~\cite{BampisDEdLMS21},
as well as a related scheduling problem~\cite{LeviMS19}. Still, it would be interesting whether learning-augmented algorithms can improve upon such probabilistic results and can add a robustness guarantee that holds for any realization. 

\medskip \noindent {\bf Acknowledgement.} We thank Alexander Lindermayr for his great support in conducting the experiments, and Michael Hoffmann for
very helpful discussions in the early phase of this research.

\newpage 
\normalsize
