# Sorting and Hypergraph Orientation under Uncertainty with Predictions

Thomas Erlebach Department of Computer Science, Durham University, United
Kingdom<EMAIL_ADDRESS>Supported by EPSRC grants EP/S033483/2
and EP/T01461X/1 Murilo Santos de Lima Munich, Germany<EMAIL_ADDRESS>Funded by EPSRC grant EP/S033483/1. Nicole Megow Faculty of Mathematics and
Computer Science, University of Bremen, Germany, {nmegow,jschloet}@uni-
bremen.de. Supported by the German Science Foundation (DFG) under contract ME
3825/1. Jens Schlöter33footnotemark: 3

###### Abstract

Learning-augmented algorithms have been attracting increasing interest, but
have only recently been considered in the setting of explorable uncertainty
where precise values of uncertain input elements can be obtained by a query
and the goal is to minimize the number of queries needed to solve a problem.
We study learning-augmented algorithms for sorting and hypergraph orientation
under uncertainty, assuming access to untrusted predictions for the uncertain
values. Our algorithms provide improved performance guarantees for accurate
predictions while maintaining worst-case guarantees that are best possible
without predictions. For hypergraph orientation, for any $\gamma\geq 2$, we
give an algorithm that achieves a competitive ratio of $1+1/\gamma$ for
correct predictions and $\gamma$ for arbitrarily wrong predictions. For
sorting, we achieve an optimal solution for accurate predictions while still
being $2$-competitive for arbitrarily wrong predictions. These tradeoffs are
the best possible. We also consider different error metrics and show that the
performance of our algorithms degrades smoothly with the prediction error in
all the cases where this is possible.

##  1 Introduction

The emerging research area of learning-augmented algorithm design has been
attracting increasing attention in recent years. For online algorithms, it was
initiated in [29] for caching and has fostered an overwhelming number of
results for numerous problems, including online graph problems [24, 28, 13, 7]
and scheduling problems [34, 3, 32, 25, 5, 6, 27, 8, 26]. In the research area
of _explorable uncertainty_ [23, 15], however, learning-augmented algorithms
have only recently been studied for the first time, namely for the minimum
spanning tree problem (MST) [17]. This area considers problems with
uncertainty in the input data assuming that a _query_ to an input element can
be used to obtain the exact value of that element. 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. Learning-augmented
algorithms in this setting are given (untrusted) predictions of the uncertain
input values. In this paper, we present and analyze learning-augmented
algorithms for further fundamental problems with explorable uncertainty,
namely sorting and hypergraph orientation.

In the _hypergraph orientation problem under uncertainty_ [9], we are given a
hypergraph $H=(V,E)$. Each vertex $v\in V$ is associated with an _uncertainty
interval_ $I_{v}=(L_{v},U_{v})$ and an, initially unknown, _precise weight_
$w_{v}\in I_{v}$. We call $L_{v}$ and $U_{v}$ the _lower and upper limit_ of
$v$. A query of $v$ reveals its precise weight $w_{v}$ and reduces its
uncertainty interval to $I_{v}=[w_{v}]$. Our task is to orient each hyperedge
$S\in E$ towards the vertex of minimum precise weight in $S$. An adaptive
algorithm can sequentially make queries to vertices to learn their weights
until it has enough information to identify the minimum-weight vertex of each
hyperedge. A set $Q\subseteq V$ is called _feasible_ if querying $Q$ reveals
sufficient information to find the orientation. As queries are costly, the
goal is to (adaptively) find a feasible query set of minimum size. An
important special case is when the input graph is a simple graph that is
exactly the interval graph induced by the uncertainty intervals $\mathcal{I}$.
This special case corresponds to the problem of sorting a set of unknown
values represented by uncertainty intervals and, therefore, we refer to it as
_sorting under uncertainty_.

Since there exist input instances that are impossible to solve without
querying all vertices, we evaluate our algorithms in an instance-dependent
manner: For each input, we compare the number of queries made by an algorithm
with the minimum possible number of queries _for that input_ , using
_competitive analysis_. For a given problem instance, let $\mathrm{OPT}$
denote an optimal query set. An algorithm is $\rho$-competitive if it
executes, for any problem instance, at most $\rho\cdot{|\mathrm{OPT}|}$
queries. As the query results are uncertain and, to a large extent, are the
deciding factor whether querying certain vertices is a good strategy or not,
the problem has a clear online flavor. In particular, the uncertainty prevents
$1$-competitive algorithms, even without any running time restrictions.

Variants of hypergraph orientation have been widely studied since the model of
explorable uncertainty has been proposed [23]. Sorting and hypergraph
orientation are well known to admit efficient polynomial-time algorithms if
precise input data is given, and they are well understood in the setting of
explorable uncertainty: The best known deterministic algorithms are
$2$-competitive, and no deterministic algorithm can be better [23, 22, 9]. For
sorting, the competitive ratio can be improved to $1.5$ using randomization
[22]. In the stochastic setting, where the precise weights of the vertices are
drawn according to known distributions over the intervals, there exists a
$1.618$-competitive algorithm for hypergraph orientation and a
$4/3$-competitive algorithm for special cases [9]. For the stochastic sorting
problem, the algorithm with the optimal expected query cost is known, but its
competitive ratio remains unknown [11]. Besides hypergraph orientation and
other selection-type problems, there has been work on combinatorial
optimization problems with explorable uncertainty, such as shortest path [18],
knapsack [20], scheduling problems [12, 4, 1, 2, 21], the minimum spanning
tree (MST) problem and matroids [16, 14, 30, 19, 31].

In this paper, we consider a third model (to the adversarial and stochastic
setting) and assume that the algorithm has, for each vertex $v$, access to a
prediction $\overline{w}_{v}\in I_{v}$ for the unknown weight $w_{v}$. These
predicted weights could for example be computed using machine learning (ML)
methods or other statistical tools on past data. Given the emerging success of
ML methods, it seems reasonable to expect predictions of high accuracy.
However, there are no theoretical guarantees and the predictions might be
arbitrarily wrong, which raises the question whether an ML algorithm performs
sufficiently well in all circumstances. In the context of hypergraph
orientation and explorable uncertainty, we answer this question affirmatively
by designing learning-augmented algorithms that perform very well if the
predictions are accurate and still match the adversarial lower bounds even if
the predictions are arbitrarily wrong. To formalize these properties, we use
the notions of $\alpha$-consistency and $\beta$-robustness [29, 34]: 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. Additionally, we aim at guaranteeing
a smooth transition between consistency and robustness by giving performance
guarantees that gracefully degrade with the _amount_ of prediction error. This
raises interesting questions regarding appropriate ways of measuring
prediction errors, and we explore several such measures. Analyzing algorithms
in terms of error-dependent consistency and robustness allows us to still give
worst-case guarantees (in contrast to the stochastic setting) that are more
fine-grained than guarantees in the pure adversarial setting.

Research on explorable uncertainty with untrusted predictions is in its
infancy. In the only previous work that we are aware of, Erlebach et al. [17]
studied the MST problem with uncertainty and untrusted predictions. They
propose an error measure $k_{h}$ called hop-distance (definition follows
later) and obtain a $1.5$-consistent and $2$-robust algorithm as well as a
parameterized consistency-robustness tradeoff with smooth degradation,
$\min\\{1+\frac{1}{\gamma}+\frac{5\cdot k_{h}}{|\mathrm{OPT}|},\gamma+1\\}$,
for any integral $\gamma\geq 2$ and error $k_{h}$. It remained open whether or
how other problems with explorable uncertainty can leverage untrusted
predictions, and what other prediction models or error metrics might be useful
in explorable uncertainty settings.

##### Main results

We show how to utilize possibly erroneous predictions for hypergraph
orientation and sorting with explorable uncertainty. For sorting, we present
an algorithm that is $1$-consistent and $2$-robust, which is in a remarkable
way best possible: the algorithm identifies an optimal query set if the
predictions are accurate, while maintaining the best possible worst-case ratio
of $2$ for arbitrary predictions. For hypergraph orientation, we give a
$1.5$-consistent and $2$-robust algorithm and show that this consistency is
best possible when aiming for optimal robustness.

Our major focus lies on a more fine-grained performance analysis with
guarantees that improve with the prediction accuracy. A key ingredient in this
line of research is the choice of error measure quantifying this (in)accuracy.
We propose and discuss three different error measures $k_{\\#},k_{h}$ and
$k_{M}$: The number of inaccurate predictions $k_{\\#}$ is natural and allows
a smooth degradation result for sorting, but in general it is too crude to
allow improvements upon lower bounds of $2$ for the setting without
predictions. We therefore also consider the _hop distance_ $k_{h}$, as
proposed in [17]. Further, we introduce a new error measure $k_{M}$ called
_mandatory query distance_ which is tailored to problems with explorable
uncertainty. It is defined in a more problem-specific way, and we show it to
be more restrictive in the sense that $k_{M}\leq k_{h}$.

For the sorting problem, we obtain an algorithm with competitive ratio
$\min\\{1+k/|\mathrm{OPT}|,2\\}$, where $k$ can be any of the three error
measures considered, which is best possible. For the hypergraph orientation
problem, 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$. 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}$. While the consistency and robustness trade-off of the
$k_{M}$-dependent algorithm is weaker, we remark that the corresponding
algorithm requires less predicted information than the $k_{h}$-dependent
algorithm and that the error dependency can be stronger as $k_{M}$ can be
significantly smaller than $k_{h}$. Further, we note that the parameter
$\gamma$ is in both results restricted to integral values since it determines
sizes of query sets, but a generalization to reals $\gamma\geq 2$ is possible
at a small loss in the guarantee. For $k_{h}$ this follows from arguments
given in [17]; for $k_{M}$ this can be shown similarly.

While our algorithm for sorting has polynomial running time, the algorithms
for the hypergraph orientation problem may involve solving an NP-hard vertex
cover problem. We justify this increased complexity by showing that even the
offline version of the problem (determining the optimal query set if the
precise weights are known) is NP-hard.

Finally, we discuss the learnability of the predictions and prove PAC-
learnability.

##  2 Preliminaries and error measures

An algorithm for the hypergraph orientation problem with uncertainty that
assumes that the predicted weights are accurate can exploit the
characterization of optimal solutions given in [9] to compute a query set that
is optimal under this assumption. Querying this set leads to $1$-consistency
but may perform arbitrarily bad in case of incorrect predictions (as shown
down below). On the other hand, known $2$-competitive algorithms for the
adversarial problems without predictions [23, 22] are not better than
$2$-consistent, and the algorithms for the stochastic setting [9] do not
guarantee any robustness at all. The known lower bounds of $2$ rule out any
robustness factor less than $2$ for our model. They build on the simple
example with a single edge $\\{u,v\\}$ and intersecting intervals
$I_{v},I_{u}$. No matter which vertex a deterministic algorithm queries first,
say $v$, the realized weight could be $w_{v}\in I_{v}\cap I_{u}$, which
requires a second query. If the adversary chooses $w_{u}\notin I_{v}\cap
I_{u}$, querying just $u$ would have been sufficient to identify the vertex of
minimum weight.

The following bound on the best achievable tradeoff between consistency and
robustness translates from the lower bound in [17] for MST under uncertainty
with predictions. Later in this paper, we provide algorithms with matching
performance guarantees. Note that this lower bound does not hold for the
sorting problem.

######  Theorem 2.1.

Let $\beta\geq 2$ be a fixed integer. For hypergraph orientation 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\\}$. The result holds
even for orienting a single hyperedge or a simple (non-hyper) graph.

The following proof is an adjusted variant of the proof in [17] of the
analogous lower bound for MST under explorable uncertainty with predictions.

###### Proof.

Assume, for the sake of contradiction, that there is a deterministic
$\beta$-robust algorithm that is $\alpha$-consistent with
$\alpha=1+\frac{1}{\beta}-\varepsilon$, for some $\varepsilon>0$. Consider an
instance with vertices $\\{0,1,\ldots,\beta\\}$, a single hyperedge that
contains all $\beta+1$ vertices, and intervals and predicted weights as in
Figure 1(a). The algorithm must query the vertices $\\{1,\ldots,\beta\\}$
first as otherwise it would query $\beta+1$ vertices in case all predictions
are correct, while there is an optimal query set of size $\beta$. Suppose
w.l.o.g. that the algorithm queries the vertices $\\{1,\ldots,\beta\\}$ in
order of increasing indices. Consider the adversarial choice
$w_{i}=\overline{w}_{i}$, for $i=1,\ldots,\beta-1$, and then $w_{\beta}\in
I_{0}$ and $w_{0}\notin I_{1}\cup\ldots\cup I_{\beta}$. This forces the
algorithm to query also $I_{0}$, while an optimal solution only queries
$I_{0}$. Thus any such algorithm has robustness at least $\beta+1$, a
contradiction.

The second part of the theorem directly follows from the first part and the
known general lower bound of $2$ on the competitive ratio [16, 23]. Assume
there is an $\alpha$-consistent deterministic algorithm with
$\alpha=1+\frac{1}{\beta^{\prime}}$ for some integer
$\beta^{\prime}\in[1,\infty)$. Consider the instance above with
$\beta=\beta^{\prime}-1$. Then the algorithm has to query the vertices
$\\{1,\ldots,\beta\\}$ first to ensure $\alpha$-consistency as otherwise it
would have a competitive ratio of
$\frac{\beta+1}{\beta}>1+\frac{1}{\beta^{\prime}}=\alpha$ in case that all
predictions are correct. By the argumentation above, the robustness factor of
the algorithm is at least $\beta+1=\beta^{\prime}=\frac{1}{\alpha-1}$.

To prove the result for the (non-hyper) graph orientation problem, the only
difference is that we use edges $\\{0,i\\}$ for $1\leq i\leq\beta$. ∎

$I_{1}$$I_{2}$$I_{\beta}$$\dots$$I_{0}$ (a)

$I_{1}$$I_{2}$$I_{n}$$\dots$$I_{n+1}$$I_{n+2}$$I_{2n}$$\dots$ (b)

Figure 1: Instances for lower bounds. Red crosses indicate predicted weights,
and green circles show correct weights. (1(a)) Lower bound on robustness-
consistency tradeoff. (1(b)) Lower bound based on the number of inaccurate
predictions.

###  2.1 Preliminaries

The crucial structure and unifying concept in hypergraph orientation and
sorting under explorable uncertainty without predictions are witness sets
[10]. Witness sets are the key to any comparison with an optimal solution. A
“classical” witness set is a set of vertices for which we can guarantee that
any feasible solution must query at least one of these vertices. In the
classical setting without access to predictions, sorting and hypergraph
orientation 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 witness pairs. The following lemma
characterizes witness pairs for our problems. We call a vertex $v$ leftmost in
a hyperedge $S$ if it is a vertex with minimum lower limit $L_{v}$ in $S$.

######  Lemma 2.2 (Kahan, 1991).

Given (hyper)graph $H=(V,E)$. Consider some $S\in E$. A set
$\\{v,u\\}\subseteq S$ with $I_{v}\cap I_{u}\neq\emptyset$, and $v$ or $u$
leftmost in $S$, is a witness set.

In terms of learning-augmented algorithms, completely relying on querying
witness pairs ensures $2$-robustness, but it does not lead to any improvements
in terms of consistency. In order to obtain an improved consistency, we need
stronger local guarantees. To that end, we call a vertex _mandatory_ , if it
is part of every feasible query set. Identifying mandatory vertices based on
the interval structure alone is not always possible, otherwise there would be
a $1$-competitive algorithm. Therefore, we want to identify vertices that are
mandatory under the assumption that the predictions are correct. We call such
vertices _prediction mandatory_. The following lemma gives a characterization
of (prediction) mandatory vertices. Recall that the uncertainty interval
$I_{v}$ of a vertex $v$ is either of form $I_{v}=(L_{v},U_{v})$ or
$I_{v}=[w_{v}]$. In the former case, we call $I_{v}$ _non-trivial_ and
otherwise we call $I_{v}$ _trivial_.

######  Lemma 2.3.

A vertex $v\in V$ with a non-trivial uncertainty interval is mandatory if and
only if there is a hyperedge $S\in E$ with $v\in S$ such that either $(i)$ $v$
is a minimum-weight vertex of $S$ and $w_{u}\in I_{v}$ for some $u\in
S\setminus\\{v\\}$, or $(ii)$ $v$ is not a minimum-weight vertex of $S$ and
$w_{u}\in I_{v}$ for the minimum-weight vertex $u$ of $S$.

###### Proof.

If $v$ is a minimum-weight vertex of hyperedge $S$ and $I_{v}$ contains
$w_{u}$ of another vertex $u\in S\setminus\\{v\\}$, then $S$ cannot be
oriented even if we query all vertices in $S\setminus\\{v\\}$ as we cannot
prove $w_{v}\leq w_{u}$ without querying $v$. If $v$ is not a minimum-weight
vertex of a hyperedge $S$ with $v\in S$ and $I_{v}$ contains the minimum
weight $w^{*}$ of $S$, then $S$ cannot be solved even if we query all vertices
in $S\setminus\\{v\\}$, as we cannot prove that $w^{*}\leq w_{v}$ without
querying $v$.

If $v$ is a minimum-weight vertex of hyperedge $S$, but $w_{u}\notin I_{v}$
for every $u\in S\setminus\\{v\\}$, then $S\setminus\\{v\\}$ is a feasible
solution for orienting $S$. If $v$ is not a minimum-weight vertex of hyperedge
$S$ and $I_{v}$ does not contain the minimum weight of $S$, then again
$S\setminus\\{v\\}$ is a feasible solution for $S$. If every hyperedge $S$
that contains $v$ falls into one of these two cases, then querying all
vertices except $v$ is a feasible query set for the whole instance. ∎

By using the lemma with the predicted weights instead of the precise weights,
we can identify prediction mandatory vertices. Furthermore, the lemma does not
only enable us to identify mandatory vertices given full knowledge of the
precise weights, but also implies criteria to identify _known mandatory_
vertices, i.e., vertices that are known to be mandatory given only the
hypergraph, the intervals, and precise weights revealed by previous queries.
Every algorithm can query such vertices without worsening its competitive
ratio as formalized by the following corollary. We call a hyperedge _not yet
solved_ , if we do not know the orientation of the hyperedge yet. In
particular, for such hyperedges, no leftmost vertex can have a trivial
uncertainty interval.

######  Corollary 2.4.

If the interval $I_{v}$ of a leftmost vertex $v$ in a not yet solved hyperedge
$S$ contains the precise weight of another vertex in $S$, then $v$ is
mandatory. In particular, if $v$ is leftmost in $S$ and $I_{u}\subseteq I_{v}$
for some $u\in S\setminus\\{v\\}$, then $v$ is mandatory.

We use Lemma 2.3 to define an offline algorithm, i.e., we assume full access
to the precise weights but still want to compute a feasible query set, that
follows a two-stage structure: First, we iteratively query all mandatory
vertices computed using Lemma 2.3. After that, each not yet oriented hyperedge
$S$ has the following configuration: The leftmost vertex $v$ has a precise
weight outside $I_{u}$ for all $u\in S\setminus\\{v\\}$, and each other vertex
in $S$ has precise weight outside $I_{v}$. Thus we can either query $v$ or all
other vertices $u\in S\setminus\\{v\\}$ with $I_{u}\cap I_{v}\not=\emptyset$
to determine the orientation. The optimum solution is to query a minimum
vertex cover in the following auxiliary graph as introduced in [9]:

######  Definition 2.5.

Given a hypergraph $H=(V,E)$, the _vertex cover instance_ of $H$ is the graph
$\bar{G}=(V,\bar{E})$ with $\\{v,u\\}\in\bar{E}$ if and only if there is a not
yet solved hyperedge $F\in E$ such that $v,u\in F$, $v$ is leftmost in $F$ and
$I_{v}\cap I_{u}\neq\emptyset$. For the sorting problem, it holds that
$\bar{G}=G$.

The Lemmas 2.2 and 2.3 directly imply that the offline algorithm is optimal.
The algorithm may require exponential time, but this is not surprising as we
also show that the offline version of the hypergraph orientation problem is
NP-hard (cf. Appendix A).

A key idea of our algorithms with access to predictions is to emulate the
offline algorithm using the predicted information. Since blindly following the
offline algorithm might lead to a competitive ratio of $n$ for faulty
predictions, we have to augment the algorithm with additional, carefully
selected queries.

The next lemma formulates a useful property of vertex cover instances without
known mandatory vertices.

######  Lemma 2.6.

Given a hypergraph $H=(V,E)$ without known mandatory vertices (by 2.4), let
$Q$ be an arbitrary vertex cover of $\bar{G}$. After querying $Q$, for each
hyperedge $F\in E$, we either know the orientation of $F$ or can determine it
by exhaustively querying according to 2.4.

###### Proof.

Consider an arbitrary hyperedge $S$ and let $v$ be leftmost in $S$. As the
instance does not contain vertices that are known mandatory by 2.4, the
leftmost vertex is unique. If the interval of $v$ is not intersected by any
$I_{u}$ with $u\in S\setminus\\{v\\}$ before querying $Q$, then we clearly
already know the orientation. Thus, assume otherwise. By assumption, we have
$I_{u}\not\subseteq I_{v}$ and $I_{v}\not\subseteq I_{u}$ for all $u\in
S\setminus\\{v\\}$ (before querying $Q$). Thus, a vertex cover of the vertex
cover instance $\bar{G}$ contains either (i) $v$, (ii) $S\setminus\\{v\\}$, or
(iii) $S$. If the vertex cover $Q$ contains the complete hyperedge $S$, then,
after querying it, we clearly know the orientation of $S$.

It remains to argue about (i) and (ii). Consider case (i) and let $u$ be
leftmost in $S\setminus\\{v\\}$. If querying $v$ reveals $w_{v}\not\in I_{u}$,
then $v$ has minimum weight in $S$ and we know the orientation of $S$. If
querying $v$ reveals $w_{v}\in I_{u}$, then the query reduces $I_{v}$ to
$[w_{v}]$ and $u$ becomes mandatory by 2.4 as $I_{v}=[w_{v}]\subseteq I_{u}$.
After querying $u$ (to exhaustively apply 2.4), we can repeat the argument
with the vertex leftmost in $S\setminus\\{u,v\\}$.

Consider case (ii). If querying $S\setminus\\{v\\}$ reveals that there exists
no vertex $u\in S\setminus\\{v\\}$ with $w_{u}\in I_{v}$, then $v$ must be of
minimum weight in $S$. Otherwise, the uncertainty interval of some $u\in
S\setminus\\{v\\}$ was reduced to $[w_{v}]\subseteq I_{v}$ and we can apply
2.4. After that, all elements of $S$ are queried and we clearly know the
orientation. ∎

###  2.2 Accuracy of predictions

While consistency and robustness only consider the extremes in terms of
prediction quality, we aim for a more fine-grained analysis that relies on
error metrics to measure the quality of the predictions. As was discussed in
[17], for the MST problem, simple error measures like the number of inaccurate
predictions $k_{\\#}=|\\{v\in V\,|\,w_{v}\not=\overline{w}_{v}\\}|$ or an
$\ell_{1}$ error metric such as $\sum_{e\in E}|w_{e}-\overline{w}_{e}|$ are
not meaningful; this is also true for the hypergraph orientation problem. In
particular, we show that even for $k_{\\#}=1$ the competitive ratio cannot be
better than the known bound of $2$ for general hypergraph orientation.

######  Theorem 2.7.

If $k_{\\#}\geq 1$, then any deterministic algorithm for the hypergraph
orientation problem under uncertainty with predictions has competitive ratio
$\rho\geq 2$. The result holds even for (non-hyper) graphs.

The following proof is an adjusted variant of the proof in [17] of the
analogous lower bound for MST under explorable uncertainty with predictions.

###### Proof.

Consider a hypergraph with vertices $\\{1,\ldots,2n\\}$, hyperedges
$S_{i}=\\{i,n+1,n+2,\ldots,2n\\}$, for $i=1,\ldots,n$, and intervals and
predicted weights as depicted in Figure 1(b). Assume w.l.o.g. that the
algorithm queries the vertices $\\{1,\ldots,n\\}$ in the order $1,2,\ldots,n$
and the vertices $\\{n+1,\ldots,2n\\}$ in the order $n+1,n+2,\ldots,2n$.
Before the algorithm queries vertex $n$ or $2n$, the adversary sets all
predictions as correct, so the algorithm will eventually query $n$ or $2n$. If
the algorithm queries $n$ before $2n$, then the adversary chooses a weight
$w_{n}$ for $n$ that forces a query to all vertices $n+1,\ldots,2n$, and the
predicted weights for those vertices as correct, so the optimum solution only
queries $n+1,\ldots,2n$. This situation is illustrated in Figure 1(b).

A symmetric argument holds if the algorithm queries vertex $2n$ before vertex
$n$.

For (non-hyper) graphs, we use edges $\\{i,j\\}$ for all $1\leq i\leq
n,n+1\leq j\leq 2n$ instead. ∎

For the sorting problem, however, we show that $k_{\\#}$-dependent guarantees
are indeed possible. In general we need more refined measures that take the
interleaving structure of intervals into account.

$I_{v_{1}}$$I_{v_{2}}$$I_{v_{3}}$$I_{v_{4}}$

$k^{+}(v_{1})=2$

$k^{+}(v_{2})=3$

$k^{+}(v_{3})=0$

$k^{+}(v_{4})=0$

$I_{v_{1}}$$I_{v_{2}}$$I_{v_{3}}$$I_{v_{4}}$

Figure 2: Example from [Erlebach _et al._ , 2022] interpreted for the
hypergraph orientation problem with a hyperedge
$S=\\{v_{1},v_{2},v_{3},v_{4}\\}$. Circles illustrate precise weights and
crosses illustrate the predicted weights. Predictions and precise weights with
a total hop distance of $k_{h}=5$ and mandatory query distance of $k_{M}=1$
(left) and $k_{h}=3$ and $k_{M}=1$ (right).

As a first refined measure, we consider the hop distance as proposed in [17].
For a vertex $v$ and any vertex $u\in V\setminus\\{v\\}$, we define the
function $k_{u}(v)$ that indicates whether the relation of $w_{v}$ to interval
$I_{u}$ changes compared to the relation of $\overline{w}_{v}$ and $I_{u}$. To
be more precise, $k_{u}(v)=1$ if $\overline{w}_{v}\leq L_{u}<w_{v}$,
$w_{v}\leq L_{u}<\overline{w}_{v}$, $w_{v}<U_{u}\leq\overline{w}_{v}$ or
$\overline{w}_{v}<U_{u}\leq w_{v}$, and $k_{u}(v)=0$ otherwise. Based on this
function, we define the hop distance of a single vertex as
$k^{+}(v)=\sum_{u\in V\setminus\\{v\\}}k_{u}(v)$. Intuitively $k^{+}(v)$ for a
single $v\in V$ counts the number of relations between $w_{v}$ and intervals
$I_{u}$ with $u\in V\setminus\\{v\\}$ that are not accurately predicted. For a
set of vertices $V^{\prime}\subseteq V$, we define
$k^{+}(V^{\prime})=\sum_{v\in V^{\prime}}k^{+}(v)$. Finally, we define the hop
distance by $k_{h}=k^{+}(V)$. For an example see Figure 2.

Note that $k_{\\#}=0$ implies $k_{h}=0$, so Theorem 2.1 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}$.

While the hop distance takes the interval structure into account, it does not
distinguish whether a “hop” affects a feasible solution. We introduce a third
and strongest error measure based on the sets of (prediction) mandatory
vertices.

Let $\mathcal{I}_{P}$ be the set of prediction mandatory vertices, and let
$\mathcal{I}_{R}$ be the set of really mandatory vertices. The _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}\Delta\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 2 (right) shows an example with $k_{M}=1$. Considering the precise
weights in the example, both $\\{v_{1}\\}$ and $\\{v_{2},v_{3},v_{4}\\}$ are
feasible solutions. Thus, no element is part of every feasible solution and
$\mathcal{I}_{R}=\emptyset$. Assuming correct predicted weights, we have that
$v_{1}$ has to be queried even if all other vertices have already been queried
and, therefore, $\mathcal{I}_{P}=\\{v_{1}\\}$. It follows
$k_{M}=|\mathcal{I}_{P}\Delta\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}$.

######  Theorem 2.8.

For any instance of hypergraph orientation under uncertainty with predictions,
the hop distance is at least as large as the mandatory query distance, i.e.,
$k_{M}\leq k_{h}$.

###### Proof.

Consider an instance with uncertainty intervals $\mathcal{I}$, precise weights
$w$ and predicted weights $\overline{w}$. Recall that $\mathcal{I}_{P}$ and
$\mathcal{I}_{R}$ are the sets of prediction mandatory vertices and mandatory
vertices, respectively. Observe that $k_{M}$ counts the vertices that are in
$\mathcal{I}_{P}\setminus\mathcal{I}_{R}$ and those that are in
$\mathcal{I}_{R}\setminus\mathcal{I}_{P}$. We will show the claim that, for
every vertex $v$ in those sets, there is a vertex $u$ such that the weight of
$u$ passes over $L_{v}$ or $U_{v}$ (or both) when going from
$\overline{w}_{v}$ to $w_{v}$. This means that each vertex
$v\in\mathcal{I}_{P}\Delta\mathcal{I}_{R}$ is mapped to a unique pair $(u,v)$
such that the weight of $u$ passes over at least one endpoint of $I_{v}$, and
hence each such pair contributes at least one to $k_{h}$. This implies
$k_{M}\leq k_{h}$.

It remains to prove the claim. Consider a
$v\in\mathcal{I}_{P}\setminus\mathcal{I}_{R}$. (The argumentation for
intervals in $\mathcal{I}_{R}\setminus\mathcal{I}_{P}$ is symmetric, with the
roles of $w$ and $\overline{w}$ exchanged.) As $v$ is not in
$\mathcal{I}_{R}$, replacing all intervals for vertices in
$\mathcal{I}\setminus\\{v\\}$ by their precise weights yields an instance that
is solved. This means that in every hyperedge $S\in E$ that contains $v$, one
of the following cases holds:

  * (a)

$v$ is known not to be the minimum of $S$ w.r.t. precise weights $w$. It
follows that there is a vertex $u$ in $S$ with $w_{u}\leq L_{v}$.

  * (b)

$v$ is known to be the minimum of $S$ w.r.t. precise weights $w$. It follows
that all vertices $u\in S\setminus\\{v\\}$ satisfy $w_{u}\geq U_{v}$.

As $v$ is in $\mathcal{I}_{P}$, replacing all intervals of vertices in
$V\setminus\\{v\\}$ by their predicted weights yields an instance that is not
solved. This means that there exists at least one hyperedge $S^{\prime}\in E$
that contains $v$ and satisfies the following:

  * (c)

All vertices $u$ in $S^{\prime}\setminus\\{v\\}$ satisfy
$\overline{w}_{u}>L_{v}$, and there is at least one such $u$ with
$L_{v}<\overline{w}_{u}<U_{v}$.

If $S^{\prime}$ falls into case (a) above, then by (a) there is a vertex $u$
in $S^{\prime}\setminus\\{v\\}$ with $w_{u}\leq L_{v}$, and by (c) we have
$\overline{w}_{u}>L_{v}$. This means that the weight of $u$ passes over
$L_{v}$. If $S^{\prime}$ falls into case (b) above, then by (c) there exists
an vertex $u$ in $S^{\prime}\setminus\\{v\\}$ with $\overline{w}_{u}<U_{v}$,
and by (b) we have $w_{u}\geq U_{v}$. Thus, the weight of $u$ passes over $v$.
This establishes the claim, and hence we have shown that $k_{M}\leq k_{h}$ for
the hypergraph orientation problem. ∎

##  3 Hypergraph orientation

We consider the general hypergraph orientation problem, and give error-
sensitive algorithms w.r.t. the measures $k_{h}$ and $k_{M}$. For $k_{h}$, we
show that we can use an adjusted variant of the algorithm given in [17] for
the MST problem.

To achieve error-sensitive guarantees w.r.t $k_{M}$, we show that the
$k_{h}$-dependent guarantee does not directly translate to $k_{M}$. Instead,
we give an even simpler algorithm that emulates the offline algorithm and
augments it with additional queries, and show that this algorithm achieves the
optimal trade-off w.r.t $k_{M}$. We remark that this algorithm only requires
access to the set of prediction mandatory vertices, which is a weaker type of
prediction than access to the predicted weights $\overline{w}$.

###  3.1 Error-sensitive algorithm w.r.t. hop distance

We start by designing an algorithm that achieves the optimal consistency and
robustness tradeoff (cf. Theorem 2.1) with a linear error dependency on the
hop distance $k_{h}$. The following theorem summarizes our main result with
respect to error measure $k_{h}$. We achieve the theorem by adjusting the
algorithm and analysis given in [17] for the MST problem. In contrast to the
result of [17], we achieve the optimal consistency-robustness tradeoff by
essentially exploiting Lemma 2.6. The corresponding analysis requires
additional work specific to the hypergraph orientation problem.

######  Theorem 3.1.

There is an algorithm for hypergraph orientation under explorable uncertainty
with predictions that, given $\gamma\in\mathbb{N}_{\geq 2}$, achieves a
competitive ratio of
$\min\\{(1+\frac{1}{\gamma})(1+k_{h}/|\mathrm{OPT}|),\gamma\\}$. If
$\gamma=2$, then the competitive ratio is
$\min\\{1.5+k_{h}/|\mathrm{OPT}|,2\\}$.

#### Overview of the algorithmic ideas

To match the lower bound on the consistency and robustness tradeoff, we, for a
given $\gamma\in\mathbb{N}_{\geq 2}$, have to guarantee
$(1+\frac{1}{\gamma})$-consistency and $\gamma$-robustness. As we observed
before, following the offline algorithm based on the predicted information can
lead to an arbitrarily bad robustness while using just the witness set
algorithm will not improve upon $2$-consistency. The idea of our algorithm
(and the one given in [17]) is to emulate the offline algorithm using the
predicted information and to combine it with the witness set algorithm.

To illustrate this idea, assume $\gamma=2$, so we have to guarantee
$1.5$-consistency and $2$-robustness. To combine both algorithms, we consider
_strengthened witness sets_ [17], which are sets $W\subseteq V$ of size three
such that every feasible solution queries at least _two_ members of $W$. If we
repeatedly query strengthened witness sets, then we achieve a competitive
ratio of at most $1.5$, matching our target consistency. Clearly, strengthened
witness sets cannot always be identified based on the given graph and
intervals alone. If we always could identify a strengthened witness set when
the instance is not solved yet, then we would have a $1.5$-competitive
algorithm by repeatedly querying such sets, contradicting the lower bound of
$2$ on the adversarial competitive ratio. Therefore, we have to identify
strengthened witness sets based on the predicted information, i.e., we
identify sets $W$ of cardinality three such that each feasible solution
contains at least two members of the set _if_ the predictions of the elements
in $W$ are correct. Since we can only identify strengthened witness sets based
on the predicted information, we cannot afford to just query the complete set,
as we might lose the guarantee on the set if the predictions are faulty, which
could violate our target $2$-robustness. To that end, we query such sets in a
carefully selected order that allows us to detect errors that might cause us
to violate the $2$-robustness after at most two queries within the set. We
select the first two queries within the set in such a way that they form a
witness set. So even if there is an error within these queries, we can discard
the third query and the two queries we already executed will never violate
$2$-robustness as they form a witness set. Furthermore, we will show that we
can charge all executed queries that violate the consistency bound to a
distinct error.

Our algorithm does this repeatedly until we cannot identify strengthened
witness sets anymore, not even by using the predictions. After that, the
instance has a certain structure that allows us to solve it with an adjusted
second phase of the offline algorithm while achieving the optimal consistency
and robustness tradeoff of Theorem 2.1 with linear error dependency on
$k_{h}$.

If $\gamma>2$, then the first phase of our algorithm repeatedly identifies a
strengthened witness set _and_ $\gamma-2$ prediction mandatory vertices. It
then queries the $\gamma-2$ prediction mandatory vertices and afterwards
proceeds to query the strengthened witness sets as described above. We show
that this adjustment allows us to achieve the optimal tradeoff with linear
dependency on $k_{h}$ for every integral $\gamma\geq 2$.

#### Precise algorithm and formal analysis

As mentioned above, our algorithm is based on identifying strengthened witness
sets using the predicted weights, i.e., sets $W\subseteq V$ with $|W|=3$ such
that every feasible solution contains at least two elements of $W$ if the
predictions are accurate. We want to be able to query $W$ in such a way that
(i) the first two queries in $W$ are a witness set and (ii) after the first
two queries in $W$ we either have detected a prediction error or can guarantee
that each feasible solution indeed contains two elements of $W$ (no matter if
the predicted weights of vertices outside $W$ are correct or not).

To achieve this, we identify prediction mandatory vertices that are not only
mandatory if all predicted weights are correct but become mandatory if a
_single_ predicted weight is correct. To that end, we use the following
definition.

######  Definition 3.2.

We say that a predicted weight $\overline{w}_{u}$ enforces another vertex $v$
if $u$ and $v$ have non-trivial uncertainty intervals, $\overline{w}_{u}\in
I_{v}$, and $u,v\in S$, where $S$ is a hyperedge such that either $v$ is
leftmost in $S$, or $u$ is leftmost in $S$ and $v$ is leftmost in
$S\setminus\\{u\\}$.

If the predicted weight $\overline{w}_{u}$ of a vertex $u$ enforces another
vertex $v$ and the predicted weight of $u$ is accurate, then after querying
$u$ we know for sure that $v$ is indeed mandatory. The following lemma
formulates this property.

######  Lemma 3.3.

If $\overline{w}_{u}$ enforces $v$, then $\\{v,u\\}$ is a witness set. Also,
if $w_{u}\in I_{v}$, then $v$ is mandatory.

###### Proof.

Since $\overline{w}_{u}$ enforces $v$, there must be a hyperedge $S$ with
$v,u\in S$ such that $\overline{w}_{u}\in I_{v}$ and either $v$ is leftmost in
$S$ or $u$ is leftmost in $S$ and $v$ is leftmost in $S\setminus\\{u\\}$. The
first claim follows from Lemma 2.2 as one of $u,v$ is leftmost in $S$ and
$I_{v}\cap I_{u}\not=\emptyset$.

If $v$ has minimum precise weight in $S$ or is leftmost in $S$, then the
second claim follows from Lemma 2.3 and Corollary 2.4. Otherwise, the fact
that $w_{u}\in I_{v}$ and that $v$ is leftmost in $S\setminus\\{u\\}$ implies
that $I_{v}$ contains the minimum precise weight, so the claim follows from
Lemma 2.3. ∎

We can now define our Algorithm 1. Within the definition of the algorithm, the
_current instance_ always refers to the problem instance obtained after
executing all previous queries. We say that a vertex is prediction mandatory
for the current instance, if it is mandatory if the predicted weight of all
_not yet queried_ vertices are correct.

The algorithm ensures that the instance never contains known mandatory
vertices according to 2.4 by exhaustively querying those vertices (cf. Lines
1, 1 and 1). The Lines 1 to 1 identify and query strengthened witness sets.
This is done by identifying a witness set $\\{u,w\\}$ such that the predicted
weight $\overline{w}_{u}$ enforces another vertex $v$. Only if $w_{u}\in
I_{v}$, the algorithm also queries $v$. If that is the case, then Lemma 3.3
implies that $v$ is mandatory and, therefore, every feasible solution must
query at least two members of $\\{u,v,w\\}$. If such a triple $\\{u,v,w\\}$ of
vertices does not exist but there still is a vertex $u$ such that
$\overline{w}_{u}$ enforces a vertex $v$, then the algorithm just queries $v$
in Line 1. We will prove that this never violates the target consistency or
robustness. If $\gamma>2$, then the algorithm precedes this step by querying
(up-to) $\gamma-2$ predictions mandatory vertices in Lines 1 to 1. The
algorithm does this repeatedly as long as possible and afterwards queries a
minimum vertex cover of the current vertex cover instance in Line 1.
Exploiting Lemma 2.6, the remaining instance can then be solved by
exhaustively querying vertices that are mandatory due to 2.4 (cf. Line 1).

Input: Hypergraph $H=(V,E)$, intervals $I_{v}$ and predictions
$\overline{w}_{v}\in I_{v}$ for all $v\in V$

1 while  _there is a known mandatory vertex $v$ by 2.4_ do query $v$;

2 repeat

3 $Q\leftarrow\emptyset$;

4 $P\leftarrow$ set of prediction mandatory vertices for the current instance;

5 while  _$P\neq\emptyset$ and $|Q|<\gamma-2$ _ do

6 pick and query some $u\in P$; $Q\leftarrow Q\cup\\{u\\}$;

7

8 while  _there is a known mandatory vertex $v$ by 2.4_ do query $v$;

9 $P\leftarrow$ set of prediction mandatory vertices for the current instance;

10

11 if  _$\exists\mbox{ distinct }u,v,w$ s.t. $\overline{w}_{u}$ enforces $v$
and $\\{u,w\\}$ is a witness set for the current instance by Lemma 2.2 _ then

12 query $u,w$;

13 if  _$w_{u}\in I_{v}$_ then query $v$ ;

14

15 else if  _$\exists v,u$ such that $\overline{w}_{u}$ enforces $v$ _ then
query $v$ ;

16 while  _there is a known mandatory vertex $v$ by 2.4_ do query $v$;

17

18until  _the current instance has no prediction mandatory vertices_ ;

19Compute and query a minimum vertex cover $Q^{\prime}$ for the current vertex
cover instance;

20 while  _there is a known mandatory vertex $v$ by 2.4_ do query $v$;

Algorithm 1 Learning-augmented algorithm for the hypergraph orientation
problem under explorable uncertainty with respect to the hop distance $k_{h}$

We proceed by proving three more important properties of the algorithm that
will help us to prove Theorem 3.1.

The Lemma 3.3 implies that if $\overline{w}_{u}$ enforces $v$ and the
predicted value of $u$ is correct, then $v$ is mandatory. This directly
implies that $v$ is prediction mandatory for the current instance: If the
predicted weight of all not yet queried vertices are correct, then the
predicted weight of $u$ is correct and $v$ is mandatory. This leads to the
following corollary.

######  Corollary 3.4.

Consider a point of execution of the algorithm in which a predicted weight
$\overline{w}_{u}$ enforces another vertex $v$. It holds that $v$ is
prediction mandatory for the current instance.

Next, we show that there is at most one iteration of the repeat-loop that
executes less than $\gamma-2$ queries in Line 1 or no queries in Lines 1–1.

######  Lemma 3.5.

Every iteration of the repeat-loop in Algorithm 1 (cf. Lines $1$–1) apart from
the final one executes $\gamma-2$ queries in Line 1 and at least one query in
Lines 1–1. Furthermore, if an iteration executes a query in Lines 1–1, then it
executes $\gamma-2$ queries in Line 1.

###### Proof.

Consider an iteration of the repeat-loop that executes less than $\gamma-2$
queries in Line 1. Then, the while-loop from Line 1 to Line 1 terminates
because the current instance has no prediction mandatory vertices. This means
that the algorithm also does not execute any queries in Lines 1–1 as there
cannot be a predicted weight $\overline{w}_{u}$ that enforces another vertex
$v$ because $v$ would be prediction mandatory for the current instance by 3.4.
Since the algorithm does not execute queries in Lines 1–1, the current
instance still does not contain prediction mandatory vertices at the end of
the current iteration of the repeat-loop, which implies that the loop
terminates.

To conclude the proof, consider an iteration of the repeat-loop that executes
$\gamma-2$ queries in Line 1 but no queries in Lines 1–1. No queries in Lines
1–1 imply that there is no $\overline{w}_{u}$ that enforces a vertex $v$.
Since the current instance contains no vertices that are mandatory by 2.4,
this means that for each hyperedge $S$ we have that (i)
$\overline{w}_{u}\not\in I_{v}$ for the unique leftmost vertex $v$ in $S$ and
all not yet queried vertices $u\in S\setminus\\{v\\}$ and (ii)
$\overline{w}_{v}\not\in I_{u}$ for the unique leftmost vertex $v$ in $S$ and
all not yet queried vertices $u\in S\setminus\\{v\\}$. If the predictions of
the not yet queried vertices are correct, then we can find the orientation of
each hyperedge $S$ by either querying the unique leftmost vertex $v$ in $S$ or
all not yet queried vertices in $S\setminus\\{u\\}$. This implies that no
vertex is prediction mandatory for the current instance and, therefore, the
loop terminates. ∎

We prove the following lemma that helps us to prove that queries in Line 1
will never violate our target consistency or robustness.

######  Lemma 3.6.

Let $u,v$ be a pair that satisfies the condition in Line 1 of Algorithm 1
leading to a query of $v$. After querying $v$, vertex $u$ will either become
mandatory by 2.4 and be queried in the next execution of Line 1 or for each
hyperedge $S$ containing $u$ we either know the orientation $S$ or know that
$u$ cannot be of minimum weight in $S$.

###### Proof.

Consider the instance before $v$ is queried. Due to the failed test in Line 1,
for every hyperedge $S$ containing $v$, the following facts hold:

  1. 1.

If $u$ is leftmost in $S$, then the orientation of $S$ is already known, or
$v\in S$ and $v$ is the only vertex in $S\setminus\\{u\\}$ with an interval
that intersects $I_{u}$.

  2. 2.

If $u$ is not leftmost in $S$ but intersects the interval of the leftmost
vertex $v^{\prime}$ in $S$, then $v=v^{\prime}$.

  3. 3.

If $u$ is not leftmost in $S$ and $I_{u}$ does not intersect the interval of
the leftmost vertex in $S$, then $u$ is certainly not of minimum weight in
$S$.

If condition (1) holds and the orientation of $S$ is not known then, after
querying $v$, either $w_{v}\notin I_{u}$ and the orientation of $S$ is
determined, or $w_{v}\in I_{u}$ and $u$ becomes mandatory by 2.4.

If condition (2) holds, then either $w_{v}\not\in I_{u}$ and $u$ is certainly
not of minimum weight in $S$, or $w_{v}\in I_{u}$ and $u$ becomes mandatory
due to Corollary 2.4. The result follows trivially if condition (3) holds. ∎

Intuitively, the lemma means that if vertex $u$ does not become mandatory by
2.4 after querying $v$, then the algorithm will _never_ even consider vertex
$u$ anymore as all hyperedges containing $u$ are either resolved or have an
orientation that is completely independent of vertex $u$. If that is the case,
then the algorithm queries _exactly_ one vertex of the witness set
$\\{u,v\\}$. This can never lead to a violation of the target consistency and
robustness as even the optimal solution has to query at least one member of
$\\{u,v\\}$. If on the other hand $u$ becomes mandatory, then either the
predicted weight $\overline{w}_{u}$ is correct and $v$ is also mandatory by
Lemma 3.3 or the predicted weight of $\overline{w}_{u}$ is wrong. In the
former case even $\mathrm{OPT}$ queries $u$ and $v$, so queries to those
vertices certainly do not lead to a violation of the target consistency. In
the latter case, $\\{u,v\\}$ is still a witness set and we will show that we
can charge one of the queries against a prediction error caused by vertex $u$,
so queries to $\\{u,v\\}$ do not violate robustness or error-dependency.

Using these insights, we are finally ready to prove Theorem 3.1.

###### Proof of Theorem 3.1.

Before we prove the performance bounds, we remark that the algorithm clearly
solves the given instance by definition of the final two lines of the
algorithm and Lemma 2.6. Next, we separately show that the algorithm executes
at most $\gamma\cdot|\mathrm{OPT}|$ queries and at most
$(1+\frac{1}{\gamma})(1+\frac{k_{h}}{|\mathrm{OPT}|})\cdot|\mathrm{OPT}|$
queries.

##### Proof of $|\mathrm{ALG}|\leq\gamma\cdot|\mathrm{OPT}|$ (robustness).

We start by proving the robustness bound. Vertices queried in Line 1 are
mandatory due to Lemma 3.3 and, thus, in any feasible solution. Clearly,
querying those vertices will never worsen the competitive ratio of
$\mathrm{ALG}$. To analyze all further queries executed by $\mathrm{ALG}$, fix
an optimum solution $\mathrm{OPT}$.

Consider an iteration of the repeat-loop in which some query is performed in
Lines 1–1. Let $P^{\prime}$ be the set of vertices queried in Lines 1, 1 and
1. If the iteration queries a vertex $v$ in Line 1 that is enforced by the
predicted weight $\overline{w}_{u}$ of a vertex $u$, then we include $u$ in
$P^{\prime}$ independent of whether the algorithm queries $u$ at some point or
not. Note that, by Lemma 3.6, such a vertex $u$ is considered in exactly one
iteration as it either is queried directly afterwards in Line 1 or will never
be considered again be the algorithm (as we argued above). Using this and the
fact that we never query vertices multiple times, we can conclude that the
sets $P^{\prime}$ of different iterations are pairwise disjoint. We continue
by showing that all such sets $P^{\prime}$ are also witness sets of size at
most $\gamma$ and, thus, querying them never violates the $\gamma$-robustness.

By Lemma 3.3, $P^{\prime}$ contains exactly $\gamma-2$ vertices queried in
Line 1. Furthermore, $P^{\prime}$ contains either two vertices $u$ and $w$
queried in Line 1 or two vertices $u$ and $v$ as considered in Line 1. Either
way, we have $|P^{\prime}|=\gamma$.

Next, we argue that $P^{\prime}$ is a witness set. If Line 1 is executed, then
note that $\\{u,w\\}\subseteq P^{\prime}$ is a witness set. If a query is
performed in Line 1, then note that $\\{v,u\\}\subseteq P^{\prime}$ is a
witness set. In both cases, $P^{\prime}$ contains a witness set and,
therefore, is a witness set itself. We conclude that $P^{\prime}$ is a witness
set of size $\gamma$ and, thus, querying $P^{\prime}$ never worsens the
competitive ratio below $\gamma$.

Let $V^{\prime}$ be the set of unqueried vertices in Line 1 during the
iteration of the repeat-loop consisting of Lines 1–1 in which no query is
performed in Lines 1–1. Recall that Lemma 3.5 states that there is at most one
such iteration and it has to be the last iteration of the loop. If no such
iteration exists, then let $V^{\prime}$ denote the set of unqueried vertices
before Line 1.

If the orientation is not yet known at this point, then the instance is not
yet solved and we have $|\mathrm{OPT}\cap V^{\prime}|\geq 1$. Furthermore,
$|Q|\leq\gamma-2$ holds for the set of queries executed in the iteration of
the repeat-loop in which no query is performed in Lines 1–1. This implies
$|Q|\leq(\gamma-2)\cdot|\mathrm{OPT}\cap V^{\prime}|$.

Let $Q^{\prime}$ denote the set of all vertices queried in Lines 1 and 1.
Since the queries of Line 1 are a minimum vertex cover for the current
instance, they are a lower bound on $|(\mathrm{OPT}\cap V^{\prime})\setminus
Q|$ by Lemma 2.2. Additionally, all queries of Line 1 are mandatory and thus
their number is at most $|\mathrm{OPT}|$. This implies that $|Q^{\prime}|\leq
2\cdot|(\mathrm{OPT}\cap V^{\prime})\setminus Q|$. Combining the bounds for
$|Q|$ and $|Q^{\prime}|$, we get
$|Q|+|Q^{\prime}|\leq\gamma\cdot|\mathrm{OPT}\cap V^{\prime}|$.

All remaining vertices queried by $\mathrm{ALG}$ have been queried in Lines 1,
1 and 1. Thus, they are mandatory, part of any feasible solution, and never
violate the $\gamma$-robustness. This concludes the proof of the robustness
bound.

##### Proof of
$|\mathrm{ALG}|\leq(1+\frac{1}{\gamma})(1+\frac{k_{h}}{|\mathrm{OPT}|})\cdot|\mathrm{OPT}|$
(consistency and error-dependency).

We continue by proving consistency and linear error-dependency. Fix an optimum
solution $\mathrm{OPT}$. Let $k^{-}(u)$ be the number of vertices $v$ such
that $v,u\in S$ for some hyperedge $S$, and the value of $v$ passes over an
endpoint of $u$, i.e., $w_{v}\leq L_{u}<\overline{w}_{v}$,
$\overline{w}_{v}\leq L_{u}<w_{v}$, $\overline{w}_{v}<U_{u}\leq w_{v}$ or
$w_{v}<U_{u}\leq\overline{w}_{v}$. From the arguments in the proof of Theorem
2.8, it can be seen that, for each vertex $u$ that is prediction mandatory at
some point during the execution of the algorithm (not necessarily for the
initially given instance) and is not in $\mathrm{OPT}$, we have that
$k^{-}(u)\geq 1$. Similar, if $u$ at some point during the execution is not
prediction mandatory for the current instance but turns out to be mandatory
for the precise weights, then $k^{-}(u)\geq 1$. For a subset $U\subseteq V$,
let $k^{-}(U)=\sum_{u\in U}k^{-}(u)$. Note that $k_{h}=k^{-}(V)$ holds by
reordering summations.

In the following, we will show for various disjoint subsets $S\subseteq V$
that $|S\cap\mathrm{ALG}|\leq(1+\frac{1}{\gamma})\cdot(|\mathrm{OPT}\cap
S|+k^{-}(S))$. The union of the subsets $S$ will contain $\mathrm{ALG}$, so it
is clear that the bound of
$(1+\frac{1}{\gamma})\cdot(1+\frac{k_{h}}{|\mathrm{OPT}|})$ on the competitive
ratio of the algorithm follows.

Vertices queried in Line 1 are in any feasible solution, so the set $P_{0}$ of
these vertices satisfies $|P_{0}|\leq|\mathrm{OPT}\cap P_{0}|$.

If there is an execution of the loop consisting of Lines 1–1 that does not
perform queries in Lines 1–1, then let $P_{1}$ be the set of vertices queried
in Line 1. Every vertex $u\in P_{1}$ is prediction mandatory, so if
$u\notin\mathrm{OPT}$ then $k^{-}(u)\geq 1$. Thus we have that
$|P_{1}|\leq|P_{1}\cap\mathrm{OPT}|+k^{-}(P_{1})$.

Let $V^{\prime}$ be the set of unqueried vertices before the execution of Line
1, and let $Q^{\prime}$ denote the vertex cover of Line 1. Since $Q^{\prime}$
is a minimum vertex cover of the vertex cover instance, we have that
$|Q^{\prime}|\leq|\mathrm{OPT}\cap V^{\prime}|$. Let $M$ be the set of
vertices queried in Line 1. Each vertex $v\in M$ is known mandatory because it
contains the precise weight $w_{u}$ of a vertex $u\in Q$. But since $v$ was
not prediction mandatory before querying $Q^{\prime}$, we have
$\overline{w}_{u}\notin I_{v}$ and, therefore, $k^{-}(v)\geq 1$. This implies
$|V^{\prime}\cap\mathrm{ALG}|=|Q^{\prime}\cup
M|\leq|V^{\prime}\cap\mathrm{OPT}|+k^{-}(M)\leq|V^{\prime}\cap\mathrm{OPT}|+k^{-}(V^{\prime})$.

Finally, consider an execution of the repeat-loop in which some query is
performed in Lines 1–1. Let $Q$ be the set of vertices queried in Line 1, and
let $W$ be the set of vertices queried in Lines 1–1. If a query is performed
in Line 1 and $u$ is queried in Line 1 directly afterwards, then include $u$
in $W$ as well. Note that $|Q|=\gamma-2$ holds by Lemma 3.5. If
$\overline{w}_{u}$ enforces $v$ in Line 1 or 1, then $v$ is prediction
mandatory due to 3.4. Also, note that $k^{-}(Q)\geq|Q\setminus\mathrm{OPT}|$,
since every vertex in $Q$ is prediction mandatory at some point. If some $v\in
Q$ is not in $\mathrm{OPT}$, then $v$ is not mandatory and, as argued above,
has $k^{-}(v)\geq 1$.

We divide the proof in three cases. For a pair $\\{v,u\\}$ as in Line 1, note
that, due to Lemma 3.5 (and as argued before the proof), $u$ is not considered
more than once, and is not considered in any of the previous cases.

  1. 1.

If $|W|=1$, then some vertex $v$ was queried in Line 1 because
$\overline{w}_{u}$ enforces $v$, and $u$ is not queried by the algorithm due
to Lemma 3.6. Then it suffices to note that $\\{v,u\\}$ is a witness set to
see that $|Q\cup W|\leq|\mathrm{OPT}\cap(Q\cup\\{u,v\\})|+k^{-}(Q)$.

  2. 2.

Consider $|W|=2$. If $W$ is a pair of the form $\\{u,w\\}$ queried in Line 1,
then $k^{-}(v)\geq 1$ because $\overline{w}_{u}$ enforces $v$ but $w_{u}\notin
I_{v}$ (as $v$ was not queried in Line 1). We can conceptually move this
contribution in the hop distance to $u$, making $k^{-}(v):=k^{-}(v)-1$ and
$k^{-}(u):=k^{-}(u)+1$. If $v$ is considered another time in Line 1 or in
another point of the analysis because it is enforced by some predicted weight,
then it has to be the predicted weight of a vertex $u^{\prime}\neq u$, so we
are not counting the contribution to the hop distance more than once. If $W$
is a pair of the form $\\{v,u\\}$ queried in Line 1 and in Line 1 directly
afterwards, then either $W\subseteq\mathrm{OPT}$ or $k^{-}(v)\geq 1$: It holds
that $u$ is mandatory, so if $v$ is not in $\mathrm{OPT}$ then it suffices to
see that $\overline{w}_{u}$ enforces $v$ to conclude that $k^{-}(v)\geq 1$.
Either way, the fact that $W$ is a witness set is enough to see that $|Q\cup
W|\leq|\mathrm{OPT}\cap(Q\cup W)|+k^{-}(Q)+k^{-}(W)$.

  3. 3.

If $|W|=3$, then $W=\\{u,v,w\\}$ as in Line 1, and $|Q\cup W|=\gamma+1$. As
$v$ is queried in Line 1, it is mandatory by Lemma 3.3. Since $\\{u,w\\}$ is a
witness set, it holds that $v$ and at least one of $\\{u,w\\}$ are contained
in any feasible solution. This implies that at least
$\frac{\gamma}{\gamma+1}\cdot|Q\cup W|-k^{-}(Q)$ of the vertices in $Q\cup W$
are in $\mathrm{OPT}$, so $|Q\cup
W|\leq(1+\frac{1}{\gamma})(|\mathrm{OPT}\cap(Q\cup W)|+k^{-}(Q))$.

The remaining vertices queried in Lines 1 and 1 are in any feasible solution
and querying them never worsens the consistency. ∎

###  3.2 An error-sensitive algorithm w.r.t. the mandatory-query distance

We continue by designing a learning-augmented algorithm with a linear error
dependency on the mandatory query distance $k_{M}$. Before we do so, we
provide the following lower bound stating that we can only hope for a slightly
worse consistency and robustness tradeoff if we want a linear error dependency
on $k_{M}$.

######  Theorem 3.7.

Let $\gamma\in\mathbb{R}_{\geq 2}$ be fixed. If a deterministic algorithm for
hypergraph orientation under explorable uncertainty with predictions is
$\gamma$-robust, then it cannot have competitive ratio better than
$1+\frac{1}{\gamma-1}$ for $k_{M}=0$. If an algorithm has competitive ratio
$1+\frac{1}{\gamma-1}$ for $k_{M}=0$, then it cannot be better than
$\gamma$-robust.

###### Proof.

We first establish the following auxiliary claim, which is slightly weaker
than the statement of the theorem:

######  Claim 3.8.

Let $\gamma^{\prime}\geq 2$ be a fixed rational number. Every deterministic
algorithm for the hypergraph orientation problem has competitive ratio at
least $1+\frac{1}{\gamma^{\prime}-1}$ for $k_{M}=0$ or has competitive ratio
at least $\gamma^{\prime}$ for arbitrary $k_{M}$.

Let $\gamma^{\prime}=\frac{a}{b}$, with integers $a\geq 2b>0$. Consider an
instance with vertices $\\{1,\ldots,a\\}$, hyperedges
$S_{i}=\\{i,b+1,b+2,\ldots,a\\}$ for $i=1,\ldots,b$, and intervals and
predicted weights as depicted in Figure 3(a). Suppose without loss of
generality that the algorithm queries vertices $\\{1,\ldots,b\\}$ in the order
$1,2,\ldots,b$, and the vertices $\\{b+1,\ldots,a\\}$ in the order
$b+1,b+2,\ldots,a$. Let the predictions be correct for $b+1,\ldots,a-1$, and
$w_{1},\ldots,w_{b-1}\notin I_{b+1}\cup\ldots\cup I_{a}$.

$I_{1}$$I_{2}$$I_{b}$$\dots$$I_{b+1}$$I_{b+2}$$I_{a}$$\dots$ (a)

$I_{1}$$I_{2}$$I_{b}$$\dots$$I_{b+1}$$I_{b+2}$$I_{a}$$\dots$ (b)

$I_{1}$$I_{2}$$I_{b}$$\dots$$I_{b+1}$$I_{b+2}$$I_{a}$$\dots$ (c)

Figure 3: Intervals, precise weights and predicted weights as used in the
lower bound instance in the proof of Theorem 3.7.

If the algorithm queries vertex $a$ before vertex $b$, then the adversary sets
$w_{a}\in I_{b}$ and $w_{b}\notin I_{a}$. (See Figure 3(b).) This forces a
query in all vertices $\\{1,\ldots,b\\}$ as they become mandatory by 2.4, so
the algorithm queries all $a$ vertices, while the optimal solution queries
only the $b$ vertices $\\{b+1,\ldots,a\\}$. Thus the competitive ratio is at
least $\frac{a}{b}=\gamma^{\prime}$ if $k_{M}$ can be arbitrarily large.

If the algorithm queries $b$ before $a$, then the adversary sets
$w_{a}=\overline{w}_{a}$ and $w_{b}\in I_{a}$; see Figure 3(c). This forces
the algorithm to query all remaining vertices in $\\{b+1,\ldots,a\\}$ as they
become mandatory by 2.4, i.e., $a$ queries in total, while the optimum queries
only the $a-b$ vertices in $\\{b+1,\ldots,a\\}$. Note, however, that
$k_{M}=0$, since the right-side vertices $\\{b+1,\ldots,1\\}$ are mandatory
for both predicted and precise weights by 2.3, while $\\{1,\ldots,b\\}$ are
neither mandatory nor prediction mandatory. Thus, the competitive ratio is at
least $\frac{a}{a-b}=1+\frac{1}{\gamma^{\prime}-1}$ for $k_{M}=0$. This
concludes the proof of 3.8.

Now we are ready to prove the theorem. Let $\gamma\geq 2$ be a fixed rational.
Assume that there is a deterministic algorithm that is $\gamma$-robust and has
competitive ratio strictly smaller than $1+\frac{1}{\gamma-1}$, say
$1+\frac{1}{\gamma+\varepsilon-1}$ with $\varepsilon>0$, for $k_{M}=0$. Let
$\gamma^{\prime}$ be a rational number with
$\gamma<\gamma^{\prime}<\gamma+\varepsilon$. Then the algorithm has
competitive ratio strictly smaller than $\gamma^{\prime}$ for arbitrary
$k_{M}$ and competitive ratio strictly smaller than
$1+\frac{1}{\gamma^{\prime}-1}$ for $k_{M}=0$, a contradiction to Claim 3.8.
This shows the first statement of the theorem.

Let $\gamma\geq 2$ again be a fixed rational. Assume that there is a
deterministic algorithm that has competitive ratio $1+\frac{1}{\gamma-1}$ for
$k_{M}=0$ and is $(\gamma-\varepsilon)$-robust, where $\varepsilon>0$. As
there is a lower bound of $2$ on the robustness of any deterministic
algorithm, no such algorithm can exist for $\gamma=2$. So we only need to
consider the case $\gamma>2$ and $\gamma-\varepsilon\geq 2$. Let
$\gamma^{\prime}$ be a rational number with
$\gamma-\varepsilon<\gamma^{\prime}<\gamma$. Then the algorithm has
competitive ratio strictly smaller than $1+\frac{1}{\gamma^{\prime}-1}$ for
$k_{M}=0$ and competitive ratio strictly smaller than $\gamma^{\prime}$ for
arbitrary $k_{M}$, a contradiction to Claim 3.8. This shows the second
statement of the theorem. ∎

This lower bound shows that the $k_{h}$-dependent guarantee of Algorithm 1
(cf. Theorem 3.1) cannot translate to the error measure $k_{M}$. Instead, for
any $\gamma\in\mathbb{N}_{\geq 2}$, we aim for a
$(1+\frac{1}{\gamma-1})$-consistent and $\gamma$-robust algorithm with linear
error dependency on $k_{M}$.

To that end, we prove the following tight bound by presenting the new
Algorithm 3 with dependency on $k_{M}$. We remark that this algorithm only
uses the initial set of prediction mandatory vertices, and otherwise ignores
the predicted weights. Since access to this set is sufficient to execute the
algorithm, it requires strictly less predicted information than the Algorithm
3 which relies on having access to the actual predicted weights.

######  Theorem 3.9.

There is an algorithm for hypergraph orientation under explorable uncertainty
with predictions that, given an integer parameter $\gamma\geq 2$, has a
competitive ratio of
$\min\\{(1+\frac{1}{\gamma-1})\cdot(1+\frac{k_{M}}{|\mathrm{OPT}|}),\gamma\\}$.

#### Overview of the algorithmic ideas

Before we give a formal proof of the theorem, we start by sketching the main
ideas. The algorithm emulates the two-stage structure of the offline
algorithm. Recall that the offline algorithm in a first stage queries all
mandatory vertices and in a second stage queries a minimum vertex cover in the
remaining vertex cover instance. Since blindly following the offline algorithm
based on the predicted weights would lead to a competitive ratio of $n$, the
algorithm augments both stages with additional queries. Algorithm 3 implements
the augmented first stage in Lines 3 to 3 and afterwards executes the second
stage.

To start the first phase, the algorithm computes the set $P$ of initial
prediction mandatory vertices (Lemma 2.3). In contrast to the
$k_{h}$-dependent algorithm, we fix the set $P$ and do _not_ recompute it when
the instance changes. Then the algorithm tries to find a vertex $p\in P$ that
is part of a witness set $\\{p,b\\}$. If $|P|\geq\gamma-1$, we query a set
$P^{\prime}\subseteq P$ of size $\gamma-1$ that includes $p$, plus $b$ (we
allow $b\in P^{\prime}$). This is clearly a witness set of size at most
$\gamma$, which ensures that the queries do not violate the
$\gamma$-robustness. Also, at least a $\frac{\gamma-1}{\gamma}$ fraction of
the queried vertices are in $P$, and every vertex in $P\setminus\mathrm{OPT}$
is in $\mathcal{I}_{P}\setminus\mathcal{I}_{R}$ and, thus, contributes to the
mandatory query distance $k_{M}$. This ensures, at least locally, that the
queried vertices do not violate the error-dependent consistency. We then
repeatedly query known mandatory vertices, remove them from $P$ and repeat
without recomputing $P$, until $P$ is empty or no vertex 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, querying a minimum vertex
cover of the current vertex cover instance and vertices that become known
mandatory by 2.4. For the second phase itself, we can use that a minimum
vertex cover of the vertex cover instance (cf. Definition 2.5) is a lower
bound on the optimal solution for the remaining instance by Lemma 2.2. Since
all queries of Line 3 are mandatory, the queries of the Lines 3 and 3 are
$2$-robust for the remaining instance. Even in combination with the additional
at most $\gamma-2$ queries of the last iteration of the loop, this is still
$\gamma$-robust. It is not hard to show that each query of Line 3 contributes
an error to $k_{M}$, which completes the argument.

Input: Hypergraph $H=(V,E)$, intervals $I_{v}$ and predictions
$\overline{w}_{v}\in I_{v}$ for all $v\in V$

1 $P\leftarrow$ set of initial prediction mandatory vertices (characterized in
Lemma 2.3);

2 while  _$\exists p\in P$ and an unqueried vertex $b$ where $\\{p,b\\}$ is a
witness set for the current instance by Lemma 2.2 _ do

3 if  _$|P|\geq\gamma-1$ _ then

4 pick $P^{\prime}\subseteq P$ with $p\in P^{\prime}$ and
$|P^{\prime}|=\gamma-1$;

5 query $P^{\prime}\cup\\{b\\}$, $P\leftarrow
P\setminus(P^{\prime}\cup\\{b\\})$;

6 while  _there is a known mandatory vertex $v$ by 2.4_ do query $v$,
$P\leftarrow P\setminus\\{v\\}$ ;

7

8 else query $P$, $P\leftarrow\emptyset$ ;

9

10Compute and query a minimum vertex cover $Q^{\prime}$ on the current vertex
cover instance;

11 while  _there is a known mandatory vertex $v$ by 2.4_ do query $v$;

Algorithm 2 Algorithm for hypergraph orientation without prediction mandatory
vertices Algorithm 3 Algorithm for hypergraph orientation under uncertainty
w.r.t. error measure $k_{M}$

#### Precise algorithm and formal analysis

We proceed by turning these arguments into a formal analysis of Algorithm 3 to
prove Theorem 3.9. To that end, we first show the following auxiliary lemma.
Recall that $\mathcal{I}_{P}$ denotes the set of (initially) prediction
mandatory vertices for the instance and $\mathcal{I}_{R}$ denotes the set of
vertices that are mandatory for the precise weights.

######  Lemma 3.10.

Every vertex queried in Line 3 of Algorithm 3 is in
$\mathcal{I}_{R}\setminus\mathcal{I}_{P}$, i.e., mandatory but not (initially)
prediction mandatory.

###### Proof.

Clearly every such vertex is in $\mathcal{I}_{R}$ because it is known to be
mandatory by 2.4, so it remains to prove that it is not in $\mathcal{I}_{P}$.
Consider a hyperedge $S$. If a vertex $u\in S\cap\mathcal{I}_{P}$ is not
queried in Line 3, then the condition for identifying a witness set in Line 3
of Algorithm 3 implies that, before Line 3 is executed, $u$ is not leftmost in
$S$ and does not intersect the leftmost vertex in $S$. Thus, $v$ cannot become
known mandatory in Line 3 and, therefore, is not queried. This implies that a
vertex queried in Line 3 cannot be contained in $\mathcal{I}_{P}$ and, thus,
the lemma. ∎

Using the auxiliary lemma, we now proceed to prove Theorem 3.9.

###### Proof of Theorem 3.9.

Before we prove the performance bounds, we remark that the algorithm clearly
solves the given instance by definition of the final two lines of the
algorithm and Lemma 2.6. Next, we separately show that the algorithm executes
at most $\gamma\cdot|\mathrm{OPT}|$ queries and at most
$(1+\frac{1}{\gamma-1})(1+\frac{k_{M}}{|\mathrm{OPT}|})\cdot|\mathrm{OPT}|$
queries.

##### Proof of $|\mathrm{ALG}|\leq\gamma\cdot|\mathrm{OPT}|$ (robustness).

Given $P^{\prime}\cup\\{b\\}$ queried in Line 3, at least one vertex is in any
feasible solution since $\\{b,p\\}$ is a witness set and, thus,
$P^{\prime}\cup\\{b\\}$ is a witness set of size $\gamma$. Therefore, querying
$P^{\prime}\cup\\{b\\}$ never worsens the robustness below $\gamma$.

Line 3 is executed at most once, since the size of $P$ never increases. Fix an
optimum solution $\mathrm{OPT}$, and let $V^{\prime}$ be the set of unqueried
vertices before Line 3 is executed (or before Line 3 if Line 3 is never
executed). Let $P$ be the set of vertices queried in Line 3, and let $Q$ be
the queries in Line 3.

If the orientation is already known before querying $P$ and $Q$, then it must
hold $P=Q=\emptyset$ and the lemma clearly holds. If the orientation is not
yet known at this point, then $|\mathrm{OPT}\cap V^{\prime}|\geq 1$, so
$|P|\leq\gamma-2$ implies $|P|\leq(\gamma-2)\cdot|\mathrm{OPT}\cap
V^{\prime}|$. Also, since $Q$ is a minimum vertex cover of the vertex cover
instance, we get $|Q|\leq|\mathrm{OPT}\cap V^{\prime}|$ by Lemma 2.2. Let $M$
be the set of vertices in $V^{\prime}$ that are queried in Line 3; clearly
$M\subseteq\mathrm{OPT}\cap V^{\prime}$ as all those vertices are mandatory.
Thus $|P|+|Q|+|M|\leq\gamma\cdot|\mathrm{OPT}\cap V^{\prime}|$.

The vertices queried in Line 3 are in any feasible solution, which implies the
robustness bound.

##### Proof of
$|\mathrm{ALG}|\leq(1+\frac{1}{\gamma-1})\cdot(1+\frac{k_{M}}{|\mathrm{OPT}|})\cdot|\mathrm{OPT}|$
(consistency and error-dependency).

Fix an optimum solution $\mathrm{OPT}$. In the following, we will show for
various disjoint subsets $J\subseteq V$ that
$|J\cap\mathrm{ALG}|\leq(1+\frac{1}{\gamma-1})\cdot(|\mathrm{OPT}\cap
J|+k_{J})$, where $k_{J}\leq|J\cap(\mathcal{I}_{P}\Delta\mathcal{I}_{R})|$.
The union of the subsets $J$ will contain $\mathrm{ALG}$, so it is clear that
the bound of $(1+\frac{1}{\gamma-1})\cdot(1+\frac{k_{M}}{|\mathrm{OPT}|})$ on
the competitive ratio of the algorithm follows.

Vertices queried in Lines 3 of Algorithm 3 are part of any feasible solution,
hence the set $P_{0}$ of these vertices satisfies
$|P_{0}|\leq|\mathrm{OPT}\cap P_{0}|$.

Given $P^{\prime}\cup\\{b\\}$ queried in Line 3, at least
$\frac{\gamma-1}{\gamma}$ of the vertices in $P^{\prime}\cup\\{b\\}$ are
prediction mandatory for the initial instance by choice of $P^{\prime}$. Among
those, let $k^{\prime}\leq k_{M}$ be the number of vertices in
$\mathcal{I}_{P}\setminus\mathcal{I}_{R}$. Then,
$|\mathrm{OPT}\cap(P^{\prime}\cup\\{b\\})|\geq\frac{\gamma-1}{\gamma}\cdot|P^{\prime}\cup\\{b\\}|-k^{\prime}$,
which gives the desired bound, i.e.,
$|P^{\prime}\cup\\{b\\}|\leq(1+\frac{1}{\gamma-1})\cdot(|\mathrm{OPT}\cap(P^{\prime}\cup\\{b\\})|+k^{\prime})$.

Every vertex queried in Line 3 that is not in $\mathrm{OPT}$ is in
$\mathcal{I}_{P}\setminus\mathcal{I}_{R}$. Hence, if there are
$k^{\prime\prime}$ such intervals, then the set $P$ of vertices queried in
Line 3 satisfies $|P|\leq|\mathrm{OPT}\cap
P|+k^{\prime\prime}<(1+\frac{1}{\gamma})\cdot(|\mathrm{OPT}\cap
P|+k^{\prime\prime})$.

Let $V^{\prime}$ be the set of unqueried vertices before Line 3 is executed,
and let $Q$ be the queries in Line 3. Then $|Q|\leq|\mathrm{OPT}\cap
V^{\prime}|$ because $Q$ is a minimum vertex cover of the vertex cover
instance, which is a lower bound on $|\mathrm{OPT}|$ by Lemma 2.2. Let $M$ be
the set of vertices that are queried in Line 3. It holds that $|Q\cup
M|\leq|\mathrm{OPT}\cap V^{\prime}|+|M|$, so the claimed bound follows from
Lemma 3.10. ∎

###  3.3 Non-integral parameter $\gamma$ via randomization

The parameter $\gamma$ in Theorems 3.1 and 3.9 is restricted to integral
values since the corresponding algorithms use it to determine sizes of query
sets. Nevertheless, a generalization to arbitrary $\gamma\in\mathbb{R}_{+}$ is
possible at a small loss in the guarantee. We give the following rigorous
upper bound on the achievable tradeoff between consistency and robustness with
linear error-dependency on $k_{M}$.

The following two theorems are shown via an adapted version of the
corresponding proof given in [17].

######  Theorem 3.11.

For any real number $\gamma\geq 2$, there is a randomized algorithm for the
hypergraph orientation problem under explorable uncertainty with predictions
that achieves a competitive ratio of
$\min\\{(1+\frac{1}{\gamma-1}+\xi)\cdot(1+\frac{k_{M}}{|\mathrm{OPT}|}),\gamma\\}$,
for $\xi\leq\frac{\gamma-\lfloor\gamma\rfloor}{(\gamma-1)^{2}}\leq 1.$

###### Proof.

For $\gamma\in\mathbb{Z}$, we run Algorithm 3 and achieve the performance
guarantee from Theorem 3.9. Assume $\gamma\notin\mathbb{Z}$, and let
$\\{\gamma\\}:=\gamma-\lfloor\gamma\rfloor=\gamma-\lceil\gamma\rceil+1$ denote
its fractional part. We run the following randomized variant of Algorithm 3.
We randomly chose $\gamma^{\prime}$ as $\lceil\gamma\rceil$ with probability
$\\{\gamma\\}$ and as $\lfloor\gamma\rfloor$ with probability
$1-\\{\gamma\\}$, and then we run the algorithm with $\gamma^{\prime}$ instead
of $\gamma$. We show that the guarantee from Theorem 3.9 holds in expectation
with an additive term less than $\\{\gamma\\}$, more precisely, we show the
competitive ratio

$\min\left\\{\left(1+\frac{1}{\gamma-1}+\xi\right)\cdot\left(1+\frac{k_{M}}{|\mathrm{OPT}|}\right),\gamma\right\\},\text{
for
}\xi=\frac{\\{\gamma\\}(1-\\{\gamma\\})}{(\gamma-1)\lfloor\gamma\rfloor(\lfloor\gamma\rfloor-1)}\leq\frac{\\{\gamma\\}}{(\gamma-1)^{2}}.$

Following the arguments in the proof of Theorem 3.9 on the robustness, the
ratio of the algorithm’s number of queries $|\mathrm{ALG}|$ and
$|\mathrm{OPT}|$ is bounded by $\gamma^{\prime}$. In expectation the
robustness is

$\displaystyle\operatorname{\mathbb{E}}\left[{\gamma^{\prime}}\right]$
$\displaystyle=(1-\\{\gamma\\})\cdot\lfloor\gamma\rfloor+\\{\gamma\\}\cdot\lceil\gamma\rceil$
$\displaystyle=(1-\\{\gamma\\})\cdot(\gamma-\\{\gamma\\})+\\{\gamma\\}\cdot(\gamma-\\{\gamma\\}+1)$
$\displaystyle=\gamma.$

The error-dependent bound on the competitive ratio is in expectation (with
$|\mathrm{OPT}|$ and $k_{M}$ not being random variables)

$\displaystyle\operatorname{\mathbb{E}}\left[\left(1+\frac{1}{\gamma^{\prime}-1}\right)\cdot\left(1+\frac{k_{M}}{|\mathrm{OPT}|}\right)\right]=\left(1+\operatorname{\mathbb{E}}\left[\frac{1}{\gamma^{\prime}-1}\right]\right)\cdot\left(1+\frac{k_{M}}{|\mathrm{OPT}|}\right).$

Applying simple algebraic transformations, we obtain

$\displaystyle\operatorname{\mathbb{E}}\left[\frac{1}{\gamma^{\prime}-1}\right]$
$\displaystyle=\frac{1-\\{\gamma\\}}{\lfloor\gamma\rfloor-1}+\frac{\\{\gamma\\}}{\lceil\gamma\rceil-1}\
=\
\frac{1-\\{\gamma\\}}{\gamma-\\{\gamma\\}-1}+\frac{\\{\gamma\\}}{\gamma-\\{\gamma\\}}$
$\displaystyle=\frac{(1-\\{\gamma\\})(\gamma-\\{\gamma\\})+\\{\gamma\\}(\gamma-\\{\gamma\\}-1)}{(\gamma-\\{\gamma\\}-1)(\gamma-\\{\gamma\\})}$
$\displaystyle=\frac{\gamma-2\\{\gamma\\}}{(\gamma-\\{\gamma\\}-1)(\gamma-\\{\gamma\\})}\
=\
\frac{1}{\gamma-1}-\frac{1}{\gamma-1}+\frac{\gamma-2\\{\gamma\\}}{(\gamma-\\{\gamma\\}-1)(\gamma-\\{\gamma\\})}$
$\displaystyle=\
\frac{1}{\gamma-1}+\frac{\\{\gamma\\}(1-\\{\gamma\\})}{(\gamma-1)(\gamma-\\{\gamma\\}-1)(\gamma-\\{\gamma\\})}\
=\
\frac{1}{\gamma-1}+\frac{\\{\gamma\\}(1-\\{\gamma\\})}{(\gamma-1)\lfloor\gamma\rfloor(\lfloor\gamma\rfloor-1)}.$

Hence, the error-dependent bound on the competitive ratio is in expectation

$\left(1+\frac{1}{\gamma-1}+\xi\right)\cdot\left(1+\frac{k_{M}}{|\mathrm{OPT}|}\right)\text{
with
}\xi=\frac{\\{\gamma\\}(1-\\{\gamma\\})}{(\gamma-1)\lfloor\gamma\rfloor(\lfloor\gamma\rfloor-1)}\leq\frac{\\{\gamma\\}}{(\gamma-1)^{2}}\leq
1,$

which concludes the proof. ∎

We can repeat essentially the same proof to obtain the analogous result for
Algorithm 1 and linear error-dependency on $k_{h}$.

######  Theorem 3.12.

For any real number $\gamma\geq 2$, there is a randomized algorithm for the
hypergraph orientation problem under explorable uncertainty with predictions
that achieves a competitive ratio of
$\min\\{(1+\frac{1}{\gamma}+\xi)\cdot(1+\frac{k_{h}}{|\mathrm{OPT}|}),\gamma\\}$,
for $\xi\leq\frac{1}{48}<0.021$.

###### Proof.

For $\gamma\in\mathbb{Z}$, we run Algorithm 1 and achieve the performance
guarantee from Theorem 3.1. Assume $\gamma\notin\mathbb{Z}$. As before, let
$\\{\gamma\\}:=\gamma-\lfloor\gamma\rfloor=\gamma-\lceil\gamma\rceil+1$ denote
its fractional part. We run the following randomized variant of Algorithm 1.
We randomly chose $\gamma^{\prime}$ as $\lceil\gamma\rceil$ with probability
$\\{\gamma\\}$ and as $\lfloor\gamma\rfloor$ with probability
$1-\\{\gamma\\}$, and then we run the algorithm with $\gamma^{\prime}$ instead
of $\gamma$. We show that the guarantee from Theorem 3.1 holds in expectation
with an additive term less than $\\{\gamma\\}$, more precisely, we show the
competitive ratio

$\min\left\\{\left(1+\frac{1}{\gamma}+\xi\right)\cdot\left(1+\frac{k_{h}}{|\mathrm{OPT}|}\right),\gamma\right\\},\text{
for
}\xi=\frac{\\{\gamma\\}(1-\\{\gamma\\})}{(\gamma-1)\lfloor\gamma\rfloor(\lfloor\gamma\rfloor-1)}\leq\frac{\\{\gamma\\}}{(\gamma-1)^{2}}.$

Exactly as in the proof of Theorem 3.11, we get
$\operatorname{\mathbb{E}}[\gamma^{\prime}]=\gamma.$ The error-dependent bound
on the competitive ratio is in expectation (with $|\mathrm{OPT}|$ and $k_{h}$
not being random variables)

$\displaystyle\operatorname{\mathbb{E}}\left[\left(1+\frac{1}{\gamma^{\prime}}\right)\cdot\left(1+\frac{k_{h}}{|\mathrm{OPT}|}\right)\right]=\left(1+\operatorname{\mathbb{E}}\left[\frac{1}{\gamma^{\prime}}\right]\right)\cdot\left(1+\frac{k_{M}}{|\mathrm{OPT}|}\right).$

Applying simple algebraic transformations, we obtain

$\displaystyle\operatorname{\mathbb{E}}\left[\frac{1}{\gamma^{\prime}}\right]$
$\displaystyle=\\{\gamma\\}\frac{1}{\lceil\gamma\rceil}+(1-\\{\gamma\\})\cdot\frac{1}{\lfloor\gamma\rfloor}$
$\displaystyle=\\{\gamma\\}\frac{1}{\lceil\gamma\rceil}+(1-\\{\gamma\\})\cdot\frac{1}{\lfloor\gamma\rfloor}\
-\ \frac{1}{\gamma}\ +\ \frac{1}{\gamma}$
$\displaystyle=\frac{1}{\gamma}+\frac{1}{\gamma\lceil\gamma\rceil\lfloor\gamma\rfloor}\cdot\bigg{(}\\{\gamma\\}\gamma\lfloor\gamma\rfloor+(1-\\{\gamma\\})\cdot\lceil\gamma\rceil\gamma-\lceil\gamma\rceil\lfloor\gamma\rfloor\bigg{)}.$

As we consider fractional $\gamma>2$, it holds
$\lceil\gamma\rceil=\lfloor\gamma\rfloor+1$. Using this, we rewrite the term
in brackets as

$\displaystyle\\{\gamma\\}\gamma\lfloor\gamma\rfloor+(1-\\{\gamma\\})\cdot(\lfloor\gamma\rfloor+1)\gamma-(\lfloor\gamma\rfloor+1)\lfloor\gamma\rfloor$
$\displaystyle=\\{\gamma\\}\gamma\lfloor\gamma\rfloor+(\lfloor\gamma\rfloor+1)\gamma-\\{\gamma\\}\cdot(\lfloor\gamma\rfloor+1)\gamma-(\lfloor\gamma\rfloor+1)\lfloor\gamma\rfloor$
$\displaystyle=(\lfloor\gamma\rfloor+1)(\gamma-\lfloor\gamma\rfloor)-\\{\gamma\\}\cdot\gamma$
$\displaystyle=\\{\gamma\\}(\lfloor\gamma\rfloor+1-\gamma)$
$\displaystyle=\\{\gamma\\}(1-\\{\gamma\\}),$

where the third and fourth equalities come from the fact that
$\gamma-\lfloor\gamma\rfloor=\\{\gamma\\}$. Note that for $\\{\gamma\\}\geq
0$, the expression $\\{\gamma\\}(1-\\{\gamma\\})$ is at most $1/4$, where it
reaches its maximum for $\\{\gamma\\}=1/2$. Further, notice that for
fractional $\gamma>2$ it holds that
$\gamma\lceil\gamma\rceil\lfloor\gamma\rfloor\geq 12$. We conclude that

$\operatorname{\mathbb{E}}{\frac{1}{\gamma^{\prime}}}\leq\frac{1}{\gamma}+\frac{\\{\gamma\\}(1-\\{\gamma\\})}{\gamma\lceil\gamma\rceil\lfloor\gamma\rfloor}\leq\frac{1}{\gamma}+\frac{1}{48}<\frac{1}{\gamma}+0.021$

which proves the theorem. ∎

##  4 Sorting under uncertainty

In this section, we consider the special case of the hypergraph orientation
problem, where the input graph is a simple graph $G=(V,E)$ that satisfies
$\\{u,v\\}\in E$ if and only if $I_{v}\cap I_{u}\not=\emptyset$. That is, $G$
corresponds to the interval graph induced by the uncertainty intervals
$\mathcal{I}=\\{I_{v}\mid v\in V\\}$. To orient such a graph, we have to, for
each pair of intersecting intervals, decide which one has the smaller precise
weight. An orientation of the graph defines an order of the intervals
according to their precise weights (and vice versa). Thus, the problem
corresponds to the problem of sorting a single set of uncertainty intervals.
Note that, by querying vertices, the uncertainty intervals change and, thus,
the graph induced by the intervals also changes. When we speak of the _current
interval graph_ , we refer to the interval graph induced by the uncertainty
intervals _after_ all previous queries.

As the main result of this section, we give a learning-augmented algorithm for
sorting under explorable with predictions that is $1$-consistent and
$2$-robust with a linear error-dependency for any
$k\in\\{k_{\\#}.k_{M},k_{h}\\}$. Clearly, no algorithm can be better than
$1$-consistent, and no deterministic algorithm can be better than $2$-robust
according to the adversarial lower bound. Before we give our algorithmic
results, we show that a sublinear error dependency is not possibly by giving a
lower bound example.

######  Theorem 4.1.

Any deterministic algorithm for sorting or hypergraph orientation under
explorable uncertainty with predictions (even for pairwise disjoint
hyperedges) has a competitive ratio
$\rho\geq\min\\{1+\frac{k}{|\mathrm{OPT}|},2\\}$, for any error measure
$k\in\\{k_{\\#},k_{M},k_{h}\\}$.

###### Proof.

Consider the input instance of the hypergraph orientation problem consisting
of a single edge $\\{v,u\\}$ with intervals and predicted weights as shown in
Figure 4.

$I_{v}$$I_{u}$ Figure 4:  Uncertainty intervals as well as the predicted and
precise weights as used in the proof of Theorem 4.1.

If the algorithm starts querying $I_{v}$, then the adversary sets
$w_{v}=\overline{w}_{v}$ and the algorithm is forced to query $u$. Then
$w_{u}\in I_{u}\setminus I_{v}$, so the optimum queries only $u$. It is easy
to see that $k_{\\#}=k_{M}=k_{h}=1$. A symmetric argument holds if the
algorithm starts querying $u$. In that case, $w_{u}=\overline{w}_{u}$ which
enforces to query $v$ with $w_{v}\in I_{v}\setminus I_{u}$. Taking multiple
copies of this instance gives the result for any $k\leq|\mathrm{OPT}|$. ∎

###  4.1 A Learning-augmented Algorithm for Sorting

As a main result of this section, we show the following upper bound that
matches Theorem 4.1.

######  Theorem 4.2.

There exists a single polynomial-time algorithm for sorting under uncertainty
with predictions that is $\min\\{1+\frac{k}{|\mathrm{OPT}|},2\\}$-competitive
for any $k\in\\{k_{\\#},k_{M},k_{h}\\}$.

The key observation that allows us to achieve improved results for orienting
interval graphs is the simple characterization of mandatory vertices: any
vertex with an interval that contains the precise weight of another vertex is
mandatory [22]. This observation is a direct consequence of Lemma 2.3 and the
structure of interval graphs. Analogously, each vertex with an interval that
contains the predicted weight of another vertex is prediction mandatory.
Furthermore, Lemma 2.2 implies that any two vertices with intersecting
intervals constitute a witness set.

To obtain a guarantee of $|\mathrm{OPT}|+k$ for any measure $k$, our algorithm
(cf. Algorithm 4) must trust the predictions as much as possible. That is, the
algorithm must behave very close to the offline algorithm under the assumption
that the predictions are correct. Recall that the offline algorithm in a first
stage queries all mandatory vertices and in a second stage queries a minimum
vertex cover in the remaining vertex cover instance after the first stage
queries. Algorithm 4 emulates again these two stages. In contrast to the
algorithms for general hypergraph orientation, we cannot afford to augment the
stages with additional queries as we aim at achieving $1$-consistency. Thus,
we need a new algorithm and cannot apply existing results.

In the emulated first phase, our algorithm queries all prediction mandatory
intervals (cf. Line 4) and all intervals that are mandatory based on the
already obtained information (cf. Lines 4 and 4). This phase clearly does not
violate the $|\mathrm{OPT}|+k$ guarantee for $k\in\\{k_{M},k_{h}\\}$, as all
queried known mandatory vertices (cf. Lines 4 and 4) are contained in
$\mathrm{OPT}$ and all queried prediction mandatory vertices (cf. Line 4) are
either in $\mathrm{OPT}$ or contribute one to $k_{M}\leq k_{h}$. We will show
that the same holds for $k=k_{\\#}$. However, the main challenge is to
guarantee $2$-robustness. Our key ingredient for ensuring this is the
following lemma, which we show in Section 4.2.

Input: Interval graph $G=(V,E)$, intervals $I_{v}$ and predictions
$\overline{w}_{v}$ for all $v\in V$

1 $\mathcal{I}_{P}\leftarrow$ set of prediction mandatory vertices;

2 while  _there is a known mandatory vertex $v$ by 2.4_ do query $v$;

3 $M_{1}\leftarrow$ vertices queried in Line 4;
$\mathcal{S}\leftarrow\mathcal{I}_{P}\setminus M_{1}$ ;

4 Query $\mathcal{S}$;

5 while  _there is a known mandatory vertex $v$ by 2.4_ do query $v$;

6 $M_{2}\leftarrow$ set of vertices queried in Line 4;

7 $\mathcal{C}\leftarrow$ Clique partition of $\mathcal{S}\cup M_{1}\cup
M_{2}$ such that all isolated vertices $v$ satisfy either $v\in M_{1}\cup
M_{2}$ or $I_{u}\cap I_{v}\not=\emptyset$ for a distinct
$u\not\in\mathcal{S}\cup M_{1}\cup M_{2}$ (computed using Lemma 4.3);

8 while  _the problem is unsolved_ do

9 let $P=x_{1}x_{2}\cdots x_{p}$ be a path component of the current interval
graph with $p\geq 2$ in direction of non-increasing lower limits $L_{x_{i}}$;

10 if  _$p$ is odd_ then query $\\{x_{2},x_{4},\ldots,x_{p-1}\\}$;

11 else

12 if  _ $x_{1}$ is the distinct partner of a critical isolated vertex $v$
($I_{x_{1}}\cap I_{v}\not=\emptyset$ and $v\not\in M_{1}\cup M_{2}$; cf. Lemma
4.3) _ then query $\\{x_{1},x_{3},\ldots,x_{p-1}\\}$;

13 else query $\\{x_{2},x_{4},\ldots,x_{p}\\}$;

14

15 while  _there is a known mandatory vertex $v$ by 2.4_ do query $v$;

16

Algorithm 4 Learning-augmented algorithm for sorting under explorable
uncertainty with predictions

######  Lemma 4.3.

For an instance of the sorting problem, let $\mathcal{I}_{P}$ be the set of
prediction mandatory vertices and $M$ the set of known mandatory vertices
after querying $\mathcal{I}_{P}$ (by exhaustively applying Corollary 2.4).
Then, we can partition $\mathcal{I}_{P}\cup M$ into a set of disjoint cliques
$\mathcal{C}$ such that each $v$ with $\\{v\\}\in\mathcal{C}$ either satisfies
$v\in M$ or $I_{v}\cap I_{u}\not=\emptyset$ for a distinct
$u\not\in\mathcal{I}_{P}\cup M$. The partition can be computed in polynomial
time.

We can apply the lemma to the queries of the first phase of the algorithm (cf.
Line 4). Given the partition $\mathcal{C}$ of the lemma, we know that queries
to vertices $v$ that are part of some $C\in\mathcal{C}$ with $|C|\geq 2$ (or
mandatory, i.e., $v\in M$) do not violate the $2$-robustness as even the
optimal solution can avoid at most one query per clique [22]. Thus, we only
have to worry about vertices $v\not\in M$ with $\\{v\\}\in\mathcal{C}$. We
call such vertices _critical isolated_ vertices. But even for critical
isolated vertices $v$, the lemma gives us a distinct not yet queried $u$ with
$I_{v}\cap I_{u}\not=\emptyset$, i.e., $\\{v,u\\}$ is a witness set.

In line with the offline algorithm, the second phase of the algorithm (cf.
Lines 4 to 4) queries a minimum vertex cover of the remaining instance (the
interval graph defined by the intervals of non-queried vertices). However, to
guarantee $2$-robustness, we have to take the witness sets of the critical
isolated vertices into account when deciding which vertex cover to query. To
see this, consider the example of Figure 5: only $v_{1}$ is prediction
mandatory, so the first phase of the algorithm just queries $v_{1}$. After
querying $v_{1}$, there are no prediction mandatory (or mandatory) vertices
left. As the only vertex queried in the first phase, $\\{v_{1}\\}$ must be
part of every clique partition. Since $v_{1}$ is not mandatory, it would
qualify as a critical isolated vertex, and $v_{2}$ is the only possible
distinct partner of $v_{1}$ with an intersecting interval that Lemma 4.3 could
assign to $v_{1}$. After querying $v_{1}$, the remaining vertex cover instance
is the path $v_{2},v_{3},v_{4},v_{5}$. One possible minimum vertex cover of
this instance is $\\{v_{3},v_{5}\\}$, but querying this vertex cover renders
$v_{2}$ and $v_{4}$ mandatory by 2.4. Thus, the algorithm would query all five
intervals, which violates the $2$-robustness as the optimal solution just
queries $\\{v_{2},v_{4}\\}$. The example illustrates that the selection of the
minimum vertex cover in the second phase is important to ensure
$2$-robustness.

$I_{v_{1}}$$I_{v_{2}}$$I_{v_{3}}$$I_{v_{4}}$$I_{v_{5}}$ Figure 5: Example
showing that it is necessary to query a specific vertex cover in the second
phase to ensure $2$-robustness. Circles illustrate precise weights and crosses
illustrate the predicted weights.

The next lemma shows that instances occurring in the second phase indeed have
a structure similar to the example by exploiting that such instances have no
prediction mandatory vertices.

######  Lemma 4.4.

Each connected component of an interval graph without prediction mandatory
vertices is either a path or a single vertex.

###### Proof.

First, observe that there are no intervals $I_{v},I_{u}$ with $I_{u}\subseteq
I_{v}$ as this would imply $\overline{w}_{u}\in I_{v}$, which contradicts the
assumption as $v$ would be prediction mandatory. Thus, the graph is a proper
interval graph. We claim that the graph contains no triangles; for proper
interval graphs, this implies that each connected component is a path, because
the 4-star $K_{1,3}$ is a forbidden induced subgraph [38]. Suppose there is a
triangle $abc$, and assume that $L_{a}\leq L_{b}\leq L_{c}$; it holds that
$U_{a}\leq U_{b}\leq U_{c}$ because no interval is contained in another. Since
$I_{a}$ and $I_{c}$ intersect, we have that $U_{a}\geq L_{c}$, so
$I_{b}\subseteq I_{a}\cup I_{c}$ and it must hold that $\overline{w}_{b}\in
I_{a}$ or $\overline{w}_{b}\in I_{c}$, a contradiction to the instance being
prediction mandatory free. ∎

Further, we observe that if the intervals of critical isolated vertices
intersect intervals of vertices on such a path component, they must also
intersect the interval of an endpoint of the component. Otherwise, the
predicted weight $\overline{w}_{v}$ of the critical isolated vertex $v$ would
be contained in the interval of at least one vertex on the path component,
which contradicts the vertices on the path not being prediction mandatory. The
distinct partner $u$ of a critical isolated vertex $v$ that exists by Lemma
4.3 is an endpoint of such a path component, as we show in Section 4.2.

The second phase of our algorithm iterates through all such connected
components and, for each component, queries a minimum vertex cover (cf. Lines
4, 4 and 4) and all resulting mandatory vertices (cf. Line 4). If the path is
of odd length, then the minimum vertex cover is unique. Otherwise, the
algorithm selects the minimum vertex cover based on whether the interval of a
critical isolated vertex intersects the interval of the first path endpoint.
This case would for example ensure that we pick the “right” vertex cover for
the example instance of Figure 5. Lemma 2.6 guarantees that the algorithm
indeed queries a feasible query set. The following lemma shows that this
strategy indeed ensures $2$-robustness by exploiting Lemma 4.3.

######  Lemma 4.5.

Algorithm 4 is $2$-robust for sorting under explorable uncertainty with
predictions.

###### Proof.

Fix an optimum solution $\mathrm{OPT}$. Let $M_{1}$, $M_{2}$ and $\mathcal{S}$
denote the phase one queries of the algorithm as defined in the pseudocode.
Consider the clique partition $\mathcal{C}$ as computed in Line 4, then all
$C\in\mathcal{C}$ with $|C|\geq 2$ satisfy $|C|\leq 2\cdot|C\cap\mathrm{OPT}|$
and all $C\in\mathcal{C}$ with $C\subseteq M_{1}\cup M_{2}$ satisfy
$|C|\leq|C\cap\mathrm{OPT}|$. The latter holds as all members of $M_{1}\cup
M_{2}$ are mandatory by 2.3. Queries to vertices that are covered by such
cliques do not violate the $2$-robustness. This leaves members of
$\mathcal{S}$ that are critical isolated vertices in $\mathcal{C}$ and queries
of the second phase. We partition such queries (and some non-queried vertices)
into a collection $\mathcal{W}$ such that, for each $W\in\mathcal{W}$, the
algorithm queries at most $2\cdot|W\cap\mathrm{OPT}|$ vertices in $W$. If we
have such a partition, then it is clear that we spend at most
$2\cdot|\mathrm{OPT}|$ queries and are $2$-robust.

By Lemma 4.3, there is a distinct vertex $u\not\in M_{1}\cup
M_{2}\cup\mathcal{S}$ for each critical isolated vertex $v$ with $I_{v}\cap
I_{u}\not=\emptyset$; as we noted above and will show in Section 4.2, $u$ is
the endpoint of a path component of the current instance before line 4. We
create the partition $\mathcal{W}$ as follows: Iteratively consider all
connected (path) components $P$ of the current instance before line 4. Let $W$
be the union of $P$ and the critical isolated vertices that are the distinct
partner of at least one endpoint of $P$. If $|W|\geq 2$, add $W$ to
$\mathcal{W}$. Then, $\mathcal{W}$ contains all critical isolated vertices of
$\mathcal{C}$ and all vertices that are queried in the Lines 4, 4, 4 and 4.

We conclude the proof by arguing that each $W\in\mathcal{W}$ satisfies that
the algorithm queries at most $2\cdot|W\cap\mathrm{OPT}|$ vertices in $W$. By
construction, $W$ contains a path component $P$ and up-to two critical
isolated vertices. Furthermore, $W$ itself is a path in the initial interval
graph (in addition to the edges of the path, there may be an additional edge
between each critical isolated vertex of $\mathcal{C}$ in $W$ and the second
or penultimate vertex of $P$, but this does not affect the argument that
follows). Consider an arbitrary $W\in\mathcal{W}$. If $|W|$ is even, then
$|W|\leq 2\cdot|W\cap\mathrm{OPT}|$ as all pairs of neighboring vertices in
path $W$ are witness pairs. Thus, assume that $|W|$ is odd. As each critical
isolated vertex has a distinct partner by Lemma 4.3 and this partner is an
endpoint of a path component, $W$ contains at most one critical isolated
vertex per distinct endpoint of $P$ and, thus, we have $|P|\geq 2$.

We divide the analysis in two cases. First assume that $|P|=p$ is odd. Then
the algorithm queries $\\{x_{2},x_{4},\ldots,x_{p-1}\\}$ in Line 4. As $P$ is
a path, the precise weight of each queried vertex can be contained in the
interval of at most one other vertex of $P$ and, therefore, force at most one
query in Line 4. This leaves at least one vertex in $P\subseteq W$ that is
never queried by the algorithm. Since
$|W\cap\mathrm{OPT}|\geq\lfloor|W|/2\rfloor$ (as the subgraph induced by $W$
contains a path of the vertices in $W$), clearly the algorithm queries at most
$2\cdot|W\cap\mathrm{OPT}|$ vertices in $W$.

Now assume that $|P|=p$ is even. Then either $x_{1}$ or $x_{p}$ (but not both)
is the distinct partner of a critical isolated member of $W$, otherwise $|W|$
would be even. If $I_{x_{1}}$ intersects the interval $I_{v}$ of the critical
isolated vertex $v$, then the algorithm queries
$\\{x_{1},x_{3},\ldots,x_{p-1}\\}$ in Line 4. If $w_{x_{1}}$ forces a query to
$x_{2}$ in Line 4 because $w_{x_{1}}\in I_{x_{2}}$, then
$|\\{x_{1},x_{2},v\\}|\leq 2\cdot|\\{x_{1},x_{2},v\\}\cap\mathrm{OPT}|$ and
the remaining vertices $W^{\prime}=W\setminus\\{x_{1},x_{2},v\\}$ form an even
path, which implies $|W^{\prime}|\leq 2\cdot|W^{\prime}\cap\mathrm{OPT}|$ and,
therefore $|W|\leq 2\cdot|W\cap\mathrm{OPT}|$. If $w_{x_{1}}$ forces no query
to $x_{2}$ in Line 4 because $w_{x_{1}}\not\in I_{x_{2}}$, then
$|\\{x_{1},v\\}|\leq 2\cdot|\mathrm{OPT}\cap\\{x_{1},v\\}|$ and we analyze
$W^{\prime}=W\setminus\\{x_{1},v\\}$ as in the subcase for odd $|P|$. Hence,
the algorithm queries at most $2\cdot|W\cap\mathrm{OPT}|$ intervals of $W$.

If $I_{x_{p}}$ intersects the interval $I_{v}$ of critical isolated member
$v$, then we can analyze $W$ analogously. ∎

######  Lemma 4.6.

Algorithm 4 spends at most $|\mathrm{OPT}|+k_{M}\leq|\mathrm{OPT}|+k_{h}$
queries.

###### Proof.

We show that the algorithm spends at most $|\mathrm{OPT}|+k_{M}$ queries.
Theorem 2.8 then implies $|\mathrm{OPT}|+k_{M}\leq|\mathrm{OPT}|+k_{h}$ . Fix
an optimum solution $\mathrm{OPT}$. Every vertex queried in Lines 4 and 4 is
in $\mathrm{OPT}$ by 2.3. Every vertex queried in Line 4 that is not in
$\mathrm{OPT}$ is clearly in $\mathcal{I}_{P}\setminus\mathcal{I}_{R}$ and
contributes one to $k_{M}$.

For each path $P$ considered in Line 4, let $P^{\prime}$ be the vertices
queried in Lines 4–4. It clearly holds that
$|P^{\prime}|\leq|P\cap\mathrm{OPT}|$. Finally, every vertex queried in Line 4
is in $\mathcal{I}_{R}\setminus\mathcal{I}_{P}$, and therefore contributes to
$k_{M}$, because we query all prediction mandatory vertices at the latest in
Line 4. ∎

###  4.2 Computing the Clique Partition

We continue by proving Lemma 4.3 and restate it here for the sake of
readability:

See 4.3

We describe how to compute a clique partition $\mathcal{C}$ of
$\mathcal{I}_{P}\cup M$ that satisfies the lemma. To that end, consider the
set $\mathcal{I}_{P}\setminus M$. The elements of $M$ are allowed to be part
of a clique of size one, so we ignore them for now. Each
$v\in\mathcal{I}_{P}\setminus M$ is prediction mandatory because it contains
the predicted weight of some other vertex $u$ (cf. 2.3 and recall that the
input instance is an interval graph). For each such $v$ we pick an arbitrary
$\pi(v)\in V$ with $\overline{w}_{\pi(v)}\in I_{v}$ as the _parent_ of $v$.
Next, we build a forest of arborescences (rooted out-trees) that contains all
vertices of $\mathcal{I}_{P}\setminus M$ (and some additional vertices) and
define it by its arcs $\mathcal{E}$. Afterwards, we use $\mathcal{E}$ to
define the clique partition of the lemma. We construct $\mathcal{E}$ by just
iteratively considering all elements $v\in\mathcal{I}_{P}\setminus M$ in an
arbitrary order and add $(\pi(v),v)$ to $\mathcal{E}$ if that does not create
a cycle. Each so constructed arborescence contains at most one vertex that is
not in $\mathcal{I}_{P}\cup M$, and this vertex has to be the root of the
arborescence.

Input: Forest of arborescences $\mathcal{E}$, set of prediction mandatory
vertices $\mathcal{I}_{P}$, set of known mandatory vertices $M$.

1 $C_{v}\leftarrow\emptyset$ for all $v\in V$;
$\mathcal{S}\leftarrow\mathcal{I}_{P}\cup M$;

2 while  _$\mathcal{S}\neq\emptyset$_ do

3 let $v$ be a deepest vertex in the forest of arborescences
$(\mathcal{I},\mathcal{E})$ among those in $\mathcal{S}$;

4 if  _$(\pi(v),v)\in\mathcal{E}$_ then

5
$C_{\pi(v)}\leftarrow\\{v^{\prime}\in\mathcal{S}:(\pi(v),v^{\prime})\in\mathcal{E}\\}$;

6 if  _$\pi(v)\in\mathcal{S}$_ then $C_{\pi(v)}\leftarrow
C_{\pi(v)}\cup\\{\pi(v)\\}$;

7 $\mathcal{S}\leftarrow\mathcal{S}\setminus C_{\pi(v)}$;

8

9 else $C_{v}\leftarrow\\{v\\}$;
$\mathcal{S}\leftarrow\mathcal{S}\setminus{C_{v}}$;

10

11return $\mathcal{C}=\\{C_{v}\mid v\in V\land C_{v}\not=\emptyset\\}$ ;

Algorithm 5 Algorithm to create a clique partition from a forest of
arborescences.

Based on $\mathcal{E}$, we create a first clique partition $\mathcal{C}$ using
Algorithm 5. Since all vertices in set $C_{v}$, as created by the algorithm,
contain the predicted weight $\overline{w}_{v}$, the created sets are clearly
cliques. Each of the partial clique partitions (created for a single
arborescence in the forest of arborescences) may contain at most a single
clique of size one. To satisfy the lemma, each such clique $\\{v\\}$ must
either satisfy $v\in M$ or needs a distinct $u\not\in\mathcal{I}_{P}\cup M$
with $I_{v}\cap I_{u}\not=\emptyset$.

If the root of the arborescence is in $M$, then the only clique $\\{v\\}$ of
size one created for the arborescence contains the root of the arborescence.
Since the root is in $M$, the cliques for the arborescence satisfy the lemma.
If the root of the arborescence is not in $\mathcal{I}_{P}\cup M$, then the
vertex $v$ in the clique of size one might not be the root of th arborescence
but a direct child of the root. In that case, the parent $\pi(v)$ of $v$ (the
vertex in the clique of size $1$) is not in $\mathcal{I}_{P}\cup M$ and we use
$\pi(v)$ as the distinct partner $u\not\in\mathcal{I}_{P}\cup M$ with
$I_{v}\cap I_{u}\not=\emptyset$ of $v$. We remark that there must be such a
$\pi(v)$ that is the endpoint of a path component in the subgraph induced by
$V\setminus(\mathcal{I}_{P}\cup M)$ as otherwise there must be a vertex $u$ on
the path with $\overline{w}_{v}\in I_{u}$; a contradiction to the vertices on
the path not being part of $\mathcal{I}_{P}$. We pick this endpoint of a path
component as the partner of $v$. In case we run into this situation for
multiple cliques $\\{v\\}$ of different arborescences but with the same
$\pi(v)$, we can just merge all those cliques into a single one. This results
in a clique as the intervals of all vertices in those smaller cliques contain
the predicted weight $\overline{w}_{\pi(v)}$.

The problematic case is when the root of the arborescence is part of
$\mathcal{I}_{P}\setminus M$. Note that this can only be the case if the
parent $\pi(r)$ of the root $r$ is also part of the arborescence, as otherwise
the corresponding edge $(\pi(r),r)$ would have been added and $r$ would not be
the root. So the parent $\pi(r)$ of the root $r$ is also part of the
arborescence but the edge $(\pi(r),r)$ was not added because it would have
created a cycle. We handle this situation by showing the following auxiliary
lemma. It states that in this case we can revise the clique partition of that
arborescence in such a way that all cliques in that clique partition for the
have size at least $2$. The auxiliary lemma then concludes the proof of Lemma
4.3.

######  Lemma 4.7.

Consider an out-tree (arborescence) $T$ on a set of prediction mandatory
vertices, where an edge $(u,v)$ represents that $\overline{w}_{u}\in I_{v}$.
Let the root be $r$. Let vertex $m$ with $\overline{w}_{m}\in I_{r}$ be a
descendant of the root somewhere in $T$. Then the vertices in $T$ can be
partitioned into cliques (sets of pairwise overlapping intervals) in such a
way that all cliques have size at least $2$.

###### Proof.

We refer to the clique partition method of Lines 5–5 in Algorithm 5 as
algorithm CP. This method will partition the nodes of an arborescence into
cliques, each consisting either of a subset of the children of a node, or of a
subset of the children of a node plus the parent of those children. In the
case considered in this lemma, all cliques will have size at least $2$, except
that the clique containing the root of the tree may have size $1$.

We first modify $T$ as follows: If there is a node $v$ in $T$ that is not a
child of the root $r$ but contains $\overline{w}_{r}$, then we make $r$ the
parent of $v$ (i.e., we remove the subtree rooted at $v$ and re-attach it
below the root). After this transformation, all vertices whose intervals
contain $\overline{w}_{r}$ are children of $r$.

Apply CP to each subtree of $T$ rooted at a child of $r$. For each of the
resulting partitions, we call the clique containing the root of the subtree
the _root clique_ of that subtree. There are several possible outcomes that
can be handled directly:

  * •

At least one of the clique partitions has a root clique of size $1$. In that
case we combine all these root cliques of size $1$ with $r$ to form a clique
of size at least $2$, and we are done: This new clique together with all
remaining cliques from the clique partitions of the subtrees forms the desired
clique partition.

  * •

All of the clique partitions have root cliques of size at least $2$, and at
least one of them has a root clique of size at least $3$. Let $s$ be the root
node of a subtree whose root clique has size at least $3$. We remove $s$ from
its clique and form a new clique from $s$ and $r$, and we are done.

  * •

All of the clique partitions have root cliques of size exactly $2$, and at
least one of the children $v$ of $r$ has $\overline{w}_{v}\in I_{r}$. Then we
add $r$ to the root clique that contains $v$. We can do this because all
intervals in that root clique contain $\overline{w}_{v}$.

Now assume that none of these cases applies, so we have the following
situation: All of the clique partitions have root cliques of size exactly $2$,
and every child $v$ of $r$ has its predicted weight outside $I_{r}$, i.e.,
$\overline{w}_{v}\notin I_{r}$. In particular, $m$, the vertex whose interval
makes $r$ prediction mandatory ($\overline{w}_{m}\in I_{r}$), cannot be a
child of $r$.

$I_{v}$$I_{r}$$I_{m}$$I_{a}$$I_{b}$$I_{q}$

Figure 6: Illustration of path from $I_{r}$ to $I_{m}$’s child $I_{q}$ in $T$

Let $T^{\prime}$ be the subtree of $T$ that is rooted at a child of $r$ and
that contains $m$. Let the root of $T^{\prime}$ be $v$.

Observe that $I_{v}$ is the only interval in $T^{\prime}$ that contains
$\overline{w}_{r}$, because all vertices with intervals containing
$\overline{w}_{r}$ are children of $r$ in $T$. Assume w.l.o.g. that
$\overline{w}_{v}$ lies to the right of $I_{r}$. Then all intervals of
vertices in $T^{\prime}$, except for $I_{v}$, lie to the right of
$\overline{w}_{r}$. See Figure 6 for an illustration of a possible
configuration of the intervals on the path from $r$ to $m$ (and a child $q$ of
$m$) in $T$.

Now re-attach the subtree $T_{m}$ rooted at $m$ as a child of $r$ (ignoring
the fact that $\overline{w}_{r}$ is not inside $I_{m}$), and let
$T_{v}=T^{\prime}\setminus T_{m}$ denote the result of removing $T_{m}$ from
$T^{\prime}$. Re-apply CP to the two separate subtrees $T_{m}$ and $T_{v}$.
The possible outcomes are:

  * •

The root clique of at least one of the two subtrees has size $1$. We can form
a clique by combining $r$ with those (one or two) root cliques of size $1$. As
both $I_{v}$ and $I_{m}$ intersect $I_{r}$ from the right, the resulting set
is indeed a clique. Together with all other cliques from the clique partitions
of $T_{m}$ and $T_{v}$, and those of the other subtrees of $r$ in $T$, we
obtain the desired clique partition.

  * •

The root cliques of both subtrees have size at least $2$. We add $r$ to the
root clique of $T_{m}$. That root clique contains only vertices with intervals
containing $\overline{w}_{m}$, and $I_{r}$ also contains $\overline{w}_{m}$,
so we do indeed get a clique if we add $r$ to that root clique. This new
clique, together with all other cliques from the clique partitions of $T_{m}$
and $T_{v}$, and those of the other subtrees of $r$ in $T$, forms the desired
clique partition.

This concludes the proof of the lemma. ∎

###  4.3 The $k_{\\#}$-dependent guarantee

We continue by proving that Algorithm 4 executes at most
$|\mathrm{OPT}|+k_{\\#}$ queries. This then concludes the proof of Theorem
4.2.

Recall that, in order to compute the clique partition of Lemma 4.7, we, for
each $v\in\mathcal{I}_{P}\setminus M$ fix an arbitrary $\pi(v)\in V$ with
$\overline{w}_{\pi(v)}\in I_{v}$ as the _parent_ of $v$. These parents will be
used in the following proofs.

To prove the $k_{\\#}$-dependent guarantee, we need the following auxiliary
lemma.

######  Lemma 4.8.

Fix the state of set $\mathcal{S}$ as in Line 4 of Algorithm 4. For each
vertex $u$, let $S_{u}=\\{v\in\mathcal{S}:\pi(v)=u\\}$. For any path $P$
considered in Line 4 and any vertex $u\in P$ that is not an endpoint of $P$,
it holds that $S_{u}=\emptyset$.

###### Proof.

Suppose for the sake of contradiction that some $u\in P$ that is not an
endpoint of $P$ has $S_{u}\neq\emptyset$. Let $a$ and $b$ be its neighbors in
$P$, and let $v\in S_{u}$. We have that $\overline{w}_{u}\notin I_{a}\cup
I_{b}$, otherwise either $a$ or $b$ would be prediction mandatory and,
therefore, have been queried in Line 4. Thus $(I_{v}\cap
I_{u})\setminus(I_{a}\cup I_{b})\neq\emptyset$, because $\overline{w}_{u}\in
I_{v}$ but $\overline{w}_{u}\not\in I_{a}\cup I_{b}$. It is not the case that
$I_{v}\subseteq I_{u}$ or $I_{u}\subseteq I_{v}$: If $I_{v}\subseteq I_{u}$,
then $u$ would have been queried in Line 4 before $P$ is considered; if
$I_{u}\subseteq I_{v}$, then $v$ would have been queried in Line 4 and
$v\notin\mathcal{S}$. Therefore it must be that $I_{v}\subseteq I_{a}\cup
I_{u}\cup I_{b}$, otherwise $I_{a}\subseteq I_{v}$ or $I_{b}\subseteq I_{v}$
(again a contradiction for $v\in\mathcal{S}$) since $(I_{v}\cap
I_{u})\setminus(I_{a}\cup I_{b})\neq\emptyset$ and $a,u,b$ forms a simple path
in the interval graph. However, if $I_{v}\subseteq I_{a}\cup I_{u}\cup I_{b}$,
then $v$ would have forced a query to $a$, $b$ or $u$ in Line 4 as one of the
corresponding intervals must contain $w_{v}$ and, thus, becomes mandatory by
Corollary 2.4. This is a contradiction to $a$,$b$ and $u$ being part of path
$P$. ∎

######  Theorem 4.9.

Algorithm 4 performs at most $|\mathrm{OPT}|+k_{\\#}$ queries.

###### Proof.

Fix an optimum solution $\mathrm{OPT}$. We partition the vertices in $V$ into
sets with the following properties. One of the sets $\tilde{S}$ contains
vertices that are not queried by the algorithm. We have a collection
$\mathcal{S}^{\prime}$ of vertex sets in which each set has at most one vertex
not in $\mathrm{OPT}$, i.e., $|S^{\prime}\setminus\mathrm{OPT}|\leq 1$ for all
$S^{\prime}\in\mathcal{S}^{\prime}$. Also, if it has one vertex not in
$\mathrm{OPT}$, then we assign a distinct prediction error to that set, in
such a way that each error is assigned to at most one set. The vertex
corresponding to the prediction error does not need to be in the same set. Let
$V^{\prime}$ be the set of vertices with a prediction error
($w_{v}\not=\overline{w}_{v}$ for all $v\in V^{\prime}$) assigned to some set
in $\mathcal{S}^{\prime}$. Finally, we have a collection $\mathcal{W}$ of
vertex sets such that for every $W\in\mathcal{W}$ it holds that
$|\mathrm{ALG}\cap W|\leq|W\cap\mathrm{OPT}|+k_{\\#}(W\setminus V^{\prime})$,
where $k_{\\#}(X)$ is the number of vertices in $X$ with incorrect
predictions. If we have such a partition, then it is clear that we spend at
most $|\mathrm{OPT}|+k_{\\#}$ queries.

We begin by adding a set that contains all vertices queried in Lines 4 and 4
($M_{1}\cup M_{2}$ in the Pseudocode) to $\mathcal{S}^{\prime}$; all such
vertices are clearly in $\mathrm{OPT}$, and we do not need to assign a
prediction error.

Fix the state of $\mathcal{S}$ as in Line 4. To deal with the vertices queried
in Line 4, we add to $\mathcal{S}^{\prime}$ the set
$S_{u}=\\{v\in\mathcal{S}:\pi(v)=u\\}$ for all $u\in V$. Note that each such
set is a clique, because the corresponding intervals of all vertices in
$S_{u}$ contain $\overline{w}_{u}$ and we are considering an interval graph.
Therefore, using Lemma 2.2, at most one vertex in $S_{u}$ is not in
$\mathrm{OPT}$, and if that occurs, then $\overline{w}_{u}\neq w_{u}$, and we
assign this prediction error to $S_{u}$.

Let $P=x_{1}x_{2}\cdots x_{p}$ with $p\geq 2$ be a path considered in Line 4,
and let $P^{\prime}$ be the set of vertices in $P$ that are queried in the
following execution of Lines 4, 4 or 4. It clearly holds that
$|P^{\prime}|=\lfloor|P|/2\rfloor\leq|P\cap\mathrm{OPT}|$ as $P$ is a path and
each edge defines a witness set Lemma 2.2. It also holds that at most
$k_{\\#}(P^{\prime})$ intervals in $P$ are queried in Line 4: Each vertex
$u\in P^{\prime}$ can force a query to at most one vertex $v$ in Line 4 as
weight $w_{u}$ can only be contained in the interval of at most one neighbor
$v$ of $u$ in the path, and in that case the predicted weight of $u$ is
incorrect because $w_{u}\in I_{v}$ but $\overline{w}_{u}\notin I_{v}$, or $v$
would have been queried in Line 4. We will create a set $W\in\mathcal{W}$ and
possibly modify $\mathcal{S}^{\prime}$, in such a way that $P\subseteq W$ and
$P^{\prime}\cap V^{\prime}=\emptyset$, so it is enough to show that

$|\mathrm{ALG}\cap W|\leq|W\cap\mathrm{OPT}|+k_{\\#}(P^{\prime}).$ (4.1)

We initially take $W$ as the vertices in $P$. By Lemma 4.8, it holds that
$S_{u}=\emptyset$ for any $u\in P$ with $u\not\in\\{x_{1},x_{p}\\}$. If
$S_{x_{1}}\subseteq\mathrm{OPT}$, then we did not assign a prediction error to
$S_{x_{1}}$. Otherwise, let $v$ be the only vertex in
$S_{x_{1}}\setminus\mathrm{OPT}$. The predicted weight of $I_{x_{1}}$ is
incorrect because $\overline{w}_{x_{1}}\in I_{v}$, and it must hold that
$x_{1}\in\mathrm{OPT}$, or $\mathrm{OPT}$ would not be able to decide the
order between $x_{1}$ and $v$ (as $I_{v}\cap I_{x_{1}}\not=\emptyset$ which
implies that $\\{v,x_{1}\\}$ is an edge and, therefore, a witness pair). If
$x_{1}\notin P^{\prime}$, then we will not use its error in the bound of
$|\mathrm{ALG}\cap W|$ to prove Equation (4.1). Otherwise, we add $v$ to $W$
and remove it from $S_{x_{1}}$, and now we do not need to assign a prediction
error to $S_{x_{1}}$ anymore as $v$ was the sole member of $S_{x_{1}}$ not in
$\mathrm{OPT}$. We do a similar procedure for $x_{p}$, and since at most one
of $x_{1},x_{p}$ is in $P^{\prime}$ by definition of Lines 4, 4 and 4, we only
have two cases to analyze: (1) $W=P$, or (2) $W=P\cup\\{v\\}$ with
$\pi(v)\in\\{x_{1},x_{p}\\}$.

  1. 1.

$W=P$. Clearly $|\mathrm{ALG}\cap
W|\leq|P^{\prime}|+k_{\\#}(P^{\prime})\leq|W\cap\mathrm{OPT}|+k_{\\#}(P^{\prime})$
as we already argued that each member of $P^{\prime}$ (the vertices queried in
Lines 4, 4 or 4) can lead to at most one additional query in Line 4 and only
if it has an incorrect predicted weight. Since in this case $|P|$ must either
be odd or $x_{1}\in P^{\prime}$ but $S_{x_{1}}\subseteq\mathrm{OPT}$ or
$x_{p}\in P^{\prime}$ but $S_{x_{p}}\subseteq\mathrm{OPT}$, we have
$P^{\prime}\cap V^{\prime}=\emptyset$.

  2. 2.

$W=P\cup\\{v\\}$, with $\pi(v)\in\\{x_{1},x_{p}\\}$. Suppose w.l.o.g. that
$\pi(v)=x_{1}$. Remember that $x_{1}\in P^{\prime}$, that
$x_{1}\in\mathrm{OPT}$, that $v\not\in\mathrm{OPT}$ and that the predicted
weight of $x_{1}$ is incorrect. Since $x_{1}\in P^{\prime}$, it holds that
$|P|$ is even and $x_{2}\notin P^{\prime}$. We have two cases.

    1. (a)

$x_{2}$ is not queried in Line 4. Then $x_{1}$ does not force a query in Line
4, so

$\displaystyle|\mathrm{ALG}\cap W|$ $\displaystyle\leq$
$\displaystyle|P^{\prime}\cup\\{v\\}|+k_{\\#}(P^{\prime}\setminus\\{x_{1}\\})$
$\displaystyle=$
$\displaystyle|P^{\prime}|+1+k_{\\#}(P^{\prime}\setminus\\{x_{1}\\})$
$\displaystyle\leq$ $\displaystyle|P\cap\mathrm{OPT}|+k_{\\#}(P^{\prime})$
$\displaystyle\leq$ $\displaystyle|W\cap\mathrm{OPT}|+k_{\\#}(P^{\prime}).$

    2. (b)

$x_{2}$ is queried in Line 4. Then $x_{1},x_{2}\in\mathrm{OPT}$, and
$|\mathrm{OPT}\cap(P\setminus\\{x_{1},x_{2}\\})|\geq|P^{\prime}\setminus\\{x_{1}\\}|$
because $|P|$ is even. Therefore,

$\displaystyle|\mathrm{ALG}\cap W|$ $\displaystyle\leq$
$\displaystyle|P^{\prime}\cup\\{x_{2},v\\}|+k_{\\#}(P^{\prime}\setminus\\{x_{1}\\})$
$\displaystyle\leq$
$\displaystyle|P\cap\mathrm{OPT}|+1+k_{\\#}(P^{\prime}\setminus\\{x_{1}\\})$
$\displaystyle\leq$ $\displaystyle|W\cap\mathrm{OPT}|+k_{\\#}(P^{\prime}).$

Finally, we add the remaining intervals that are not queried by the algorithm
to $\tilde{S}$. ∎

##  5 Learnability of predictions

In this section, we argue about the learnability of our predictions with
regard to the different error measures for a given instance of hypergraph
orientation $H=(V,E)$ with the set of uncertainty intervals
$\mathcal{I}=\\{I_{v}\mid v\in V\\}$.

We assume that the realization $w$ of precise weights for $\mathcal{I}$ is
i.i.d. drawn from an unknown distribution $D$, and that we can i.i.d. sample
realizations from $D$ to obtain a training set. Let $\mathcal{H}$ denote the
set of all possible prediction vectors $\overline{w}$, with
$\overline{w_{v}}\in I_{v}$ for each $I_{v}\in\mathcal{I}$. Let
$k_{h}(w,\overline{w})$ denote the hop distance of the prediction
$\overline{w}$ for the realization with the precise weights $w$. Since $w$ is
drawn from $D$, the value $k_{h}(w,\overline{w})$ is a random variable.
Analogously, we consider $k_{M}(w,\overline{w})$ with regard to the mandatory
query distance. Our goal is to learn predictions $\overline{w}$ that
(approximately) minimize the expected error $\operatorname{\mathbb{E}}_{w\sim
D}[k_{h}(w,\overline{w})]$ respectively $\operatorname{\mathbb{E}}_{w\sim
D}[k_{M}(w,\overline{w})]$. In the following, we argue separately about the
learnability with respect to $k_{h}$ and $k_{M}$.

Note that, under the PAC-learning assumption that we can sample the precise
weights, it is also possible to apply the algorithm for the stochastic problem
variant given in [9]. However, in contrast to the results of this paper, the
guarantee of the algorithm given in [9] holds in expectation instead of in the
worst-case and admits no robustness. Furthermore, our algorithms work as a
blackbox independent of how the predictions are obtained.

###  5.1 Learning with respect to the hop distance

The following theorem states the learnability w.r.t. $k_{h}$ and directly
follows from the (problem independent) learnability proof in [17].

######  Theorem 5.1.

For any $\varepsilon,\delta\in(0,1)$, there exists a learning algorithm that,
using a training set of size $m$, returns predictions
$\overline{w}\in\mathcal{H}$, such that $\operatorname{\mathbb{E}}_{w\sim
D}[k_{h}(w,\overline{w})]\leq\operatorname{\mathbb{E}}_{w\sim
D}[k_{h}(w,\overline{w}^{*})]+\varepsilon$ holds with probability at least
$(1-\delta)$, where
$\overline{w}^{*}=\arg\min_{\overline{w}^{\prime}\in\mathcal{H}}\operatorname{\mathbb{E}}_{w\sim
D}[k_{h}(w,\overline{w}^{\prime})]$. The sample complexity is
$m\in\mathcal{O}\left(\frac{(\log(n)-\log(\delta/n))\cdot(2n)^{2}}{(\varepsilon/n)^{2}}\right)$
and the running time is polynomial in $m$ and $n$.

###  5.2 Learning with respect to the mandatory query distance

We argue about the learnability w.r.t. $k_{M}$. Since each $I_{v}$ is an open
interval, there are infinitely many predictions $\overline{w}$, and, thus, the
set $\mathcal{H}$ is also infinite. In order to reduce the size of
$\mathcal{H}$, we discretize each $I_{v}$ by fixing a finite number of
potentially predicted weights $\overline{w}_{v}$ of $I_{v}$ using the same
technique as in [17].

We define the set $\mathcal{H}_{v}$ of predicted weights for $v$ as follows.
Let $\\{B_{1},\ldots,B_{l}\\}$ be the set of lower and upper limits of
intervals in $\mathcal{I}\setminus\\{I_{v}\\}$ that are contained in $I_{v}$.
Assume that $B_{1},\ldots,B_{l}$ are indexed by increasing value. Let
$B_{0}=L_{v}$ and $B_{l+1}=U_{v}$ and, for each $j\in\\{0,\ldots,l\\}$, let
$h_{j}$ be an arbitrary value of $(B_{j},B_{j+1})$. We define
$\mathcal{H}_{v}=\\{B_{1},\ldots,B_{l},h_{0},\ldots,h_{l}\\}$. Since two
weights $\overline{w}_{v},\overline{w}_{v}^{\prime}\in(B_{j},B_{j+1})$ always
lead to the same hop distance $k^{+}(v)$ for vertex $v$, there will always be
an element of $\mathcal{H}_{v}$ that minimizes the expected hop distance for
$v$. Each $\mathcal{H}_{v}$ contains at most $\mathcal{O}(n)$ values. Then,
the discretized $\mathcal{H}$ is the Cartesian product of all discretized
$\mathcal{H}_{v}$ with $v\in V$ and, thus, the distcretzation reduces the size
of $\mathcal{H}$ to at most $\mathcal{O}(n^{n})$.

The following lemma shows that we do not lose any precision by using the
discretized $\mathcal{H}$. Here, for any vector $\overline{w}$ of predicted
weights, $\mathcal{I}_{\overline{w}}$ denotes the set of prediction mandatory
vertices. In particular, $\mathcal{H}$ is now finite.

######  Lemma 5.2.

For a given instance of the hypergraph orientation problem with intervals
$\mathcal{I}$, let $\overline{w}$ be a vector of predicted weights that is not
contained in the discretized $\mathcal{H}$. Then, there is a
$\overline{w}^{\prime}\in\mathcal{H}$ such that
$\mathcal{I}_{\overline{w}}=\mathcal{I}_{\overline{w}^{\prime}}$.

The lemma implies that, for each $\overline{w}$, there is an
$\overline{w}^{\prime}\in\mathcal{H}$ that has the same error w.r.t. $k_{M}$
as $\overline{w}$. Thus, there always exists an element $\overline{w}$ of the
discretized $\mathcal{H}$ such that $\overline{w}$ minimizes the expected
error over all possible vectors of predicted weights.

###### Proof of Lemma 5.2.

Given the vector of predicted weights $\overline{w}$, we construct a vector
$\overline{w}^{\prime}\in\mathcal{H}$ that satisfies the lemma.

For each $\overline{w}_{v}$, we construct $\overline{w}^{\prime}_{v}$ as
follows: If $\overline{w}_{v}=B_{j}$ for some $j\in\\{1,\ldots,l\\}$, then we
set $\overline{w}_{v}^{\prime}=B_{j}$, where $B_{j}$ is defined as in the
definition of the discretized $\mathcal{H}_{v}$. Otherwise it must hold
$\overline{w}_{v}\in(B_{j},B_{j+1})$ for some $j\in\\{1,\ldots,l\\}$, and we
set $\overline{w}^{\prime}_{v}=h_{j}$. Then, for each $u\in
V\setminus\\{v\\}$, it holds $\overline{w}_{v}\in I_{u}$ if and only if
$\overline{w}_{v}^{\prime}\in I_{u}$.

We show that each $v\in\mathcal{I}_{\overline{w}}$ is also contained in
$\mathcal{I}_{\overline{w}^{\prime}}$. Since $v$ is mandatory assuming precise
weights $\overline{w}$, Lemma 2.3 implies that there is a hyperedge $S$ such
that either (i) $\overline{w}_{v}$ is the minimum weight of $S$ and
$\overline{w}_{u}\in I_{v}$ for some $u\in S\setminus\\{v\\}$ or (ii)
$\overline{w}_{v}$ is not the minimum weight of $S$ but contains the weight
$\overline{w}_{u}$ of the vertex $u$ with minimum weight $\overline{w}_{u}$ in
$S$.

Assume $v$ satisfies case (i) for the predicted weights $\overline{w}$. By
construction of $\overline{w}^{\prime}$ it then also holds
$\overline{w}^{\prime}_{u}\in I_{v}$. Thus, if $v$ has minimum weight in $S$
for the weights $\overline{w}^{\prime}$, then
$v\in\mathcal{I}_{\overline{w}^{\prime}}$ by Lemma 2.3. Otherwise, some
$v^{\prime}\in S\setminus\\{v\\}$ must have the minimum weight
$\overline{w}^{\prime}_{v^{\prime}}$ in $S$ for the weights
$\overline{w}^{\prime}$. Since $v$ has minimum weight for the weights
$\overline{w}$, it must hold
$\overline{w}^{\prime}_{v^{\prime}}<\overline{w}^{\prime}_{v}$ but
$\overline{w}_{v^{\prime}}\geq\overline{w}_{v}$. By construction of
$\overline{w}^{\prime}$, this can only be the case if
$\overline{w}^{\prime}_{v^{\prime}},\overline{w}_{v^{\prime}}\in I_{v}$. This
implies that $v$ satisfies case (ii) for the weights $\overline{w}^{\prime}$
and, therefore $v\in\mathcal{I}_{\overline{w}^{\prime}}$ by Lemma 2.3.

Assume $v$ satisfies case (ii) for the predicted weights $\overline{w}$. By
construction of $\overline{w}^{\prime}$ it then also holds
$\overline{w}^{\prime}_{u}\in I_{v}$. Thus, if $u$ has minimum weight in $S$
for the weights $\overline{w}^{\prime}$, then
$v\in\mathcal{I}_{\overline{w}^{\prime}}$. Otherwise, some $u^{\prime}\in
S\setminus\\{u\\}$ must have minimum weight in $S$ for the weights
$\overline{w}^{\prime}$. If $u^{\prime}=v$, then $v$ satisfies case (i) for
the weights $\overline{w}^{\prime}$ and, therefore,
$v\in\mathcal{I}_{\overline{w}^{\prime}}$ by Lemma 2.3. If $u^{\prime}\not=u$,
then it must hold
$\overline{w}^{\prime}_{u^{\prime}}<\overline{w}^{\prime}_{u}$ but
$\overline{w}_{u^{\prime}}\geq\overline{w}_{u}$ as $u$ has minimum weight in
$S$ for weights $\overline{w}$ but $u^{\prime}$ has minimum weight in $S$ for
weights $\overline{w}^{\prime}$. By construction and since
$\overline{w}_{u}\in I_{v}$, this can only be the case if
$\overline{w}^{\prime}_{u^{\prime}},\overline{w}_{u^{\prime}}\in I_{v}$. This
implies that $v$ satisfies case (ii) for the weights $\overline{w}^{\prime}$
and therefore $v\in\mathcal{I}_{\overline{w}^{\prime}}$ by Lemma 2.3.

Symmetrically, we can show that each $v\in\mathcal{I}_{\overline{w}^{\prime}}$
is also contained in $\mathcal{I}_{\overline{w}}$, which implies
$\mathcal{I}_{\overline{w}}=\mathcal{I}_{\overline{w}^{\prime}}$. ∎

Recall that $k_{M}$ is defined as
$k_{M}=|\mathcal{I}_{P}\Delta\mathcal{I}_{R}|$, where $\mathcal{I}_{P}$ is the
set of predictions mandatory vertices and $\mathcal{I}_{R}$ is the set of
mandatory vertices. In contrast to learning predictions $\overline{w}$ w.r.t.
$k_{h}$, a vertex $v\in\mathcal{I}$ being part of
$\mathcal{I}_{P}\Delta\mathcal{I}_{R}$ depends not only on $\overline{w}_{v}$
and $w_{v}$, but on the predicted and precise weights of vertices
$V\setminus\\{v\\}$. Thus, the events of $v$ and $u$ with $v\not=u$ being part
of $\mathcal{I}_{P}\Delta\mathcal{I}_{R}$ are not necessarily independent.
Therefore, we cannot separately learn the predicted weights $\overline{w}_{v}$
for each $v\in V$, which is a major difference to the proof for $k_{h}$ in
[17]. The approach in [17] learns the predicted weights separately in order to
achieve a polynomial running time.

Since the discretized $\mathcal{H}$ is still finite and $k_{M}$ is bounded by
$[0,n]$, we still can apply _empirical risk minimization (ERM)_ to achieve
guarantees similar to the ones of Theorem 5.1. However, because we cannot
learn the $\overline{w}_{v}$ separately, we would have to find the element of
$\mathcal{H}$ that minimizes the empirical error. ERM first i.i.d. samples a
trainingset $S=\\{w^{1},\ldots,w^{m}\\}$ of $m$ precise weights vectors from
$D$. Then, it returns the predicted weights $\overline{w}\in\mathcal{H}$ that
minimizes the _empirical error_
$k_{S}(\overline{w})=\frac{1}{m}\sum_{j=1}^{m}k_{M}(w^{j},\overline{w})$. As
$\mathcal{H}$ is of exponential size, a straightforward implementation of ERM
requires exponential running time. We use this straightforward implementation
to prove the following theorem.

######  Theorem 5.3.

For any $\varepsilon,\delta\in(0,1)$, there exists a learning algorithm that,
using a training set of size $m$, returns predictions
$\overline{w}\in\mathcal{H}$, such that $\operatorname{\mathbb{E}}_{w\sim
D}[k_{M}(w,\overline{w})]\leq\operatorname{\mathbb{E}}_{w\sim
D}[k_{M}(w,\overline{w}^{*})]+\varepsilon$ holds with probability at least
$(1-\delta)$, where
$\overline{w}^{*}=\arg\min_{\overline{w}^{\prime}\in\mathcal{H}}\operatorname{\mathbb{E}}_{w\sim