\subsection{Proof of Theorem~\ref{thm:lb1setuniform}}

\theoremLBSingleSetUniform*

\begin{proof}
Consider $n+1$ elements $e_0, \ldots, e_n$, with $I_0 = (0, 2)$ and $I_i = (1, 3)$ for $i > 0$, and uniform query costs $c_i = 1$ for all $i$.
The probabilities are such that $\mathbb{P}[v_0 \in (1, 2)] = \frac{n-1}{n}$ and $\mathbb{P}[v_i \in (1, 2)] = \epsilon$ for all $i > 0$, with some $0 < \epsilon \ll \frac{n-1}{n}$.
It is easy to show that $\EX[\ensuremath{\mathrm{OPT}}] = n - \frac{n-1}{n}(1-\epsilon)^n$, which tends to $\frac{n^2 - n + 1}{n}$ as $\epsilon$ approaches $0$.
By the argumentation in~\cite[Section~3]{chaplick20stochasticLATIN}, the best decision tree either queries $e_0$ and then all other elements if $v_0 \in (1, 2)$, or it queries $e_1, \ldots, e_n$ adaptively (in an order that does not matter for this instance since they are all identical) until either a query is forced in $e_0$ (when some $v_i \in (0, 1)$ with $i > 0$) or the problem is solved by querying all elements except $e_0$ (when $v_i \in [1, 2)$ for all $i > 0$).
The first decision tree clearly has expected query cost $1 + n \cdot \mathbb{P}[v_0 \in (1, 2)] = n$.
The expected query cost of the second decision tree can be computed with the following recurrence, where $A(k)$ is the cost of the subtree for elements $e_0$ and $e_{n-k+1}, \ldots, e_n$:
\begin{displaymath}
 \left\{ \begin{array}{l} A(1) = 1 + \epsilon \\ A(k) = 1 + \epsilon \cdot \left( 1 + \frac{n-1}{n} \cdot (k -1) \right) + (1-\epsilon) \cdot A(k-1) \end{array} \right.
\end{displaymath}
It is easy to show by induction that $A(k) = k - \frac{k}{n} + \left( 1 + \frac{1}{n\epsilon}\right)(1 - (1-\epsilon)^k)$, so we have that
$A(n) = n - (1-\epsilon)^n + \frac{1 - (1-\epsilon)^n}{n \epsilon}$ and therefore
\begin{displaymath}
 \lim_{\epsilon \rightarrow 0} A(n) = n - 1 + \lim_{\epsilon \rightarrow 0} \frac{1 - (1-\epsilon)^n}{n \epsilon} =  n - 1 + \lim_{\epsilon \rightarrow 0} \frac{n(1-\epsilon)^{n-1}}{n} = n - 1 + 1  = n,
\end{displaymath}
where the second equality follows by L'Hôpital's rule.
For either decision tree, the competitive ratio tends to ${n^2}/({n^2-n+1})$ as $\epsilon$ approaches $0$.
\end{proof}
\subsection{Proof of Theorem~\ref{theorem:VC_based_LB}}

\theoremVCbasedLB*

\begin{proof}
	\begin{figure}[tbh]
		\centering
		\begin{tikzpicture}[line width = 0.3mm]
		\interval{$x$}{0}{3}{0}
		\interval{$y$}{1}{4}{-0.5}
		\interval{$z$}{2}{5}{-1}
		
		\draw[dotted] (1, 0.5) -- (1, -1.5);
		\draw[dotted] (2, 0.5) -- (2, -1.5);
		\draw[dotted] (3, 0.5) -- (3, -1.5);
		
		\node at (0.5, 0.2) {$\epsilon$};
		\node at (1.5, 0.25) {$0$};
		\node at (2.5, 0.23) {$1 - \epsilon$};
		
		\node at (1.5, -0.3) {$1/2$};
		\node at (2.5, -0.26) {$0$};
		\node at (3.5, -0.3) {$1/2$};
		
		\node at (2.5, -0.8) {$\epsilon$};
		\node at (4, -0.8) {$1 - \epsilon$};
		
		\node at (6.5, 0) {$c_x = k$};
		\node at (6.5, -0.5) {$c_y = 1$};
		\node at (6.5, -1) {$c_z = k$};
		\end{tikzpicture}
		\caption{Lower bound example for orienting a single hyperedge.}
		\label{Ex_1}
	\end{figure}
	
	\textbf{Case 1.} Consider the instance of Figure~\ref{Ex_1}.
	Each two-stage algorithm has to query a vertex cover for the vertex cover instance in the first stage. 
	Otherwise, it is not guaranteed that the problem can be solved in the second stage while only querying mandatory elements.
	Thus, each algorithm either queries $A_1 = \{x\}$, $A_2 = \{y, z\}$ or a superset of one of them in the first stage.
	Since querying supersets of $A_1$ or $A_2$ in the first stage never improves in comparison to just querying $A_1$ or $A_2$, we discard that option. 
	For $\epsilon$ tending to zero, the expected cost of the two-stage algorithms are
	$\EX[A_1] = \EX[A_2] = k + 1 + \frac{1}{2} \cdot k = \frac{3}{2} \cdot k + 1$,
	while the expected optimum is 
	$\EX[\ensuremath{\mathrm{OPT}}] = 1 + \frac{1}{2} \cdot k + \frac{1}{2} \cdot k = k+1$
	and therefore, for $k$ tending to infinity, the competitive ratio approaches $\frac{3}{2}$.
	\begin{figure}[tb]
		\centering
		\begin{tikzpicture}[line width = 0.3mm]
		\interval{$x_1$}{0}{3}{1}
		\path (-0.3, 0) -- (-0.3, 1) node[font=\normalsize, midway, sloped]{$\dots$};
		\interval{$x_k$}{0}{3}{0}
		\interval{$y$}{1}{4}{-0.5}
		\interval{$z_1$}{2}{5}{-1}
		\path (1.7, -1) -- (1.7, -2) node[font=\normalsize, midway, sloped]{$\dots$};
		\interval{$z_k$}{2}{5}{-2}
		
		\draw[dotted] (1, 1.5) -- (1, -2.5);
		\draw[dotted] (2, 1.5) -- (2, -2.5);
		\draw[dotted] (3, 1.5) -- (3, -2.5);
		
		\node at (0.5, 1.2) {$\epsilon$};
		\node at (1.5, 1.25) {$0$};
		\node at (2.5, 1.23) {$1 - \epsilon$};
		
		\node at (0.5, 0.2) {$\epsilon$};
		\node at (1.5, 0.25) {$0$};
		\node at (2.5, 0.23) {$1 - \epsilon$};
		
		\node at (1.5, -0.3) {$1/2$};
		\node at (2.5, -0.26) {$0$};
		\node at (3.5, -0.3) {$1/2$};
		
		\node at (2.5, -0.8) {$\epsilon$};
		\node at (4, -0.8) {$1 - \epsilon$};
		
		\node at (2.5, -1.8) {$\epsilon$};
		\node at (4, -1.8) {$1 - \epsilon$};
		\end{tikzpicture}
		\qquad
		\begin{tikzpicture}[thick, scale=0.5]
		\draw (0, 0) node[vertex, label=west:$x_1$]{} -- (4, 0) node[vertex, label=east:$z_1$]{};
		\draw (0, 0) -- (4, 1.5) node[vertex, label=east:$y$]{};
		\draw (0, -3) node[vertex, label=west:$x_k$]{} -- (4, -3) node[vertex, label=east:$z_k$]{};
		\draw (0, 0) -- (4, -3);
		\draw (0, -3) -- (4, 1.5);
		\draw (0, -3) -- (4, 0);
		
		\path (-0.8, 0) -- (-0.8, -3) node[font=\normalsize, midway, sloped]{$\dots$};
		\path (4.7, 0) -- (4.7, -3) node[font=\normalsize, midway, sloped]{$\dots$};
		
		\path (0.6, 0.5) -- (0.6, -3) node[font=\normalsize, midway, sloped]{$\dots$};
		\path (3.2, 0) -- (3.2, -3) node[font=\normalsize, midway, sloped]{$\dots$};
		\end{tikzpicture}
		\caption{Lower bound example for the hyperedge orientation problem.
			The vertex cover instance is shown in the complete bipartite graph at the right.}
		\label{Ex_2}
	\end{figure}

	\textbf{Case 2.} The argumentation is analogous to the proof of the first case but uses the instance in Figure~\ref{Ex_2}.
	The hyperedges are $S_1, \ldots, S_k$, with $S_i = \{x_i, y, z_1, \ldots, z_k\}$.
	
\textbf{Case~3.} The argumentation is analogous to the proof of Case~$1$ but uses the instance in Figure~\ref{Ex_3}.
		\begin{figure}[tb]
		\centering
		\begin{tikzpicture}[line width = 0.3mm]
		\interval{$x_1$}{0}{3}{1}
		\path (-0.3, 0) -- (-0.3, 1) node[font=\normalsize, midway, sloped]{$\dots$};
		\interval{$x_k$}{0}{3}{0}
		\intervalcolor{$y$}{1}{4}{-0.5}{red}
		\interval{$z_1$}{2}{5}{-1}
		\path (1.7, -1) -- (1.7, -2) node[font=\normalsize, midway, sloped]{$\dots$};
		\interval{$z_k$}{2}{5}{-2}
		
		\draw[dotted] (1, 1.5) -- (1, -2.5);
		\draw[dotted] (2, 1.5) -- (2, -2.5);
		\draw[dotted] (3, 1.5) -- (3, -2.5);
		
		\node at (0.5, 1.2) {$1- \epsilon$};
		\node at (1.5, 1.25) {$0$};
		\node at (2.5, 1.23) {$\epsilon$};
		
		\node at (0.5, 0.2) {$1 - \epsilon$};
		\node at (1.5, 0.25) {$0$};
		\node at (2.5, 0.23) {$\epsilon$};
		
		\node[red] at (1.5, -0.3) {$1/2$};
		\node[red] at (2.5, -0.26) {$0$};
		\node[red] at (3.5, -0.3) {$1/2$};
		
		\node at (2.5, -0.8) {$\epsilon$};
		\node at (4, -0.8) {$1 - \epsilon$};
		
		\node at (2.5, -1.8) {$\epsilon$};
		\node at (4, -1.8) {$1 - \epsilon$};
		\end{tikzpicture}
		\qquad
		\begin{tikzpicture}[thick, scale=0.5]
		\draw (0, 1) node[vertex, label=west:$x_1$]{} -- (4, 1) node[vertex, label=east:$z_1$]{};
		\draw (0, 0) node[vertex, label=west:$x_2$]{} -- (4, 0) node[vertex, label=east:$z_2$]{};
		\draw (0, -3) node[vertex, label=west:$x_k$]{} -- (4, -3) node[vertex, label=east:$z_k$]{};
		\draw (0, 0) -- (4, 1);
		\draw (0, 0) -- (4, -3);
		\draw (0, 1) -- (4, 0);
		\draw (0, 1) -- (4, -3);
		\draw (0, -3) -- (4, 1);
		\draw (0, -3) -- (4, 0);
		
		\begin{scope}[on background layer]
		\draw[red] (2, -4) node[red, fill=red, vertex, label=south:$y$]{} -- (0, -3);
		\draw[red] (2, -4) -- (4, -3);
		\draw[red] plot (2, -4) to [bend left=30] (0, 0);
		\draw[red] plot (2, -4) to [bend left=45] (0, 1);
		\draw[red] plot (2, -4) to [bend right=30] (4, 0);
		\draw[red] plot (2, -4) to [bend right=45] (4, 1);
		\end{scope}
		
		\path (-0.8, 0) -- (-0.8, -3) node[font=\normalsize, midway, sloped]{$\dots$};
		\path (4.7, 0) -- (4.7, -3) node[font=\normalsize, midway, sloped]{$\dots$};
		
		\path (0.6, 0) -- (0.6, -3) node[font=\normalsize, midway, sloped]{$\dots$};
		\path (3.2, 0) -- (3.2, -3) node[font=\normalsize, midway, sloped]{$\dots$};
		\end{tikzpicture}
		\caption{Lower bound example for the graph orientation problem with uniform query costs.
			The subgraph induced by $\{x_1, \ldots x_k, z_1, \ldots, z_k\}$ is complete bipartite, and $y$ is a universal vertex (adjacent to all others).}
		\label{Ex_3}
	\end{figure}
\end{proof}


\section{Appendix for Section~\ref{sec:preliminaries}}
\label{app:preliminaries}

\subsection{Proof of Lemma~\ref{lemma:mandatory}}
\lemmamandatory*

\begin{proof}
	If~$v$ is a minimum-weight vertex of~$F$ and $w_u \in I_v$ for another vertex $u\in F \setminus \{v\}$, then~$F$ cannot be oriented even if we query all vertices in $F \setminus \{v\}$.
	If~$v$ is not a minimum-weight vertex of~$F$ and contains the weight $w_u$ of the minimum-weight vertex $u$ of $F$, then~$F$ cannot be oriented even if we query all vertices in $F \setminus \{v\}$, as we cannot prove that $w_u \leq w_v$.
	
	If~$v$ is a minimum-weight vertex of~$F$, but $w_u \notin I_v$ for every $u \in F \setminus \{v\}$, then $F \setminus \{v\}$ is a feasible query set for orienting $F$.
	If~$v$ is not a minimum-weight vertex of~$F$ and does not contain the weight $w_u$ of a minimum-weight vertex of~$F$, then again $F \setminus \{v\}$ is a feasible query set for orienting $F$. If every hyperedge $F$ 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.
\end{proof}

\subsection{Proof of \#P-hardness}
\label{app:sharpP}

\begin{theorem}
\label{thm:sharpPhard}
Computing $p_v$ for a hypergraph $H=(V,E)$ is \#P-hard, even if all hyperedges have size~$3$.
\end{theorem}

\begin{proof}
The proof consists of a reduction of the \#P-hard problem of counting the number of vertex covers of a given graph $G=(V,E)$.  We construct the following instance to the hypergraph orientation problem.  

Let $v'$ be a new vertex, which does not belong to $V$. We construct the hypergraph $H=(V\cup\{v'\}, E')$, where every edge $\{u,v\}\in E$ from the original graph corresponds to an hyperedge in $E'$ of the form $\{u,v,v'\}$.  The value $w_v$ associated to every vertex $v\in V$ follows a distribution on the interval $I_v = (i\varepsilon, 2+i\varepsilon)$ for an
arbitrary $\varepsilon$ with $0 < \varepsilon < 1/n$, where $i$ is the rank of $v$ for some arbitrary fixed ordering of $V$.  The role of the shift by $\varepsilon$ is to avoid inclusion of the intervals. The distribution on
$I_v$ is constructed such that the variable $v$ is less than~$1$ with probability $1/2$
and at least~$1$ with probability $1/2$. 
The value associated to vertex $v'$ belongs to the interval $[1,2+(n+1) \varepsilon]$.  

What is the probability	that $v'$ is mandatory? For every realization of the
vertices, it is only crucial which of them have value less than $1$.  Let
$T\subseteq V$ be the set of the vertices with a value below the threshold $1$.  Every
potential set $T$ has the same probability $1/2^n$. 

Now $v'$ becomes mandatory by a set $\{u,v,v'\}$ if and only if both
values $w_u,w_v$ are at least~$1$.  This means that $v'$ is \emph{not} mandatory if and
only if the set $T$ defined by the realization is a vertex cover
for the graph $G$.  In other words the probability that $v'$ is mandatory
equals $1-\ell/2^n$, where $\ell$ is the number of vertex covers of $G$. 
As a consequence, computing this probability is \#P-hard.
\end{proof}

\subsection{Proof of Lemma~\ref{lem:sampling}}
\lemsampling*

\begin{proof}
The algorithm consists of drawing independently $k =\lceil \ln(2/\delta)/(2\epsilon^2) \rceil$ realizations of the vertex values, and determining for each realization whether $v$ is mandatory by using Lemma~\ref{lemma:mandatory}.  
The output $y$ is the fraction of realizations where this event happened.


For the analysis, let $X_v^i$ be the random variable indicating whether $v$ is mandatory in the $i$-th realization. These variables are independent and have mean $p_v$.  Using Hoeffding's concentration bound we have
\begin{align*}
	{\mathbb P}\left[\left|\frac1k\sum_{i=1}^k X_v^i - p_v\right| > \epsilon\right] &< 2 \exp(-2k\epsilon^2)
\end{align*}
The choice of $k$ is motivated by the following equivalent inequalties.
\begin{align*}
	2\exp(-2k \epsilon^2) & \leq \delta
	\\
	-2k \epsilon^2 & \leq \ln(\delta/2)
	\\
	k &\geq \ln(2/\delta)/(2 \epsilon^2).
\end{align*}
For the time complexity we observe that verifying if a vertex is mandatory can be done in time $O(|V|^2)$.
Its practical implementation makes use of the given probability matrix. Let $t_1,\ldots,t_{2|V|}$ be the sorted elements of $\{\ell_v,r_v|v\in V\}$, defining elementary intervals of the form $(t_i, t_{i+1})$.  The given probability matrix specifies for every given vertex $v\in V$ the probability that its weight $w_v$ belongs to a given interval $(t_i,t_{i+1})$.  Instead of sampling the actual weights, we only sample the elementary intervals to which they belong. Hence, for a fixed sample, 
we know for each hyperedge $E$ in which elementary interval $M$ its minimum weight lies.
In this setting, the vertices that are mandatory because of $E$ can be determined as follows:
\begin{itemize}
	\item If at least two weights of vertices in $E$ belong to~$M$, then all vertices $v\in E$ with $M\subseteq I_v=(\ell_v,r_v)$ are mandatory.
	\item Otherwise, let $m\in E$ be the unique vertex whose weight lies in $M$. We then have:
	\begin{itemize}
		\item Every other vertex $u\in E$ with $M\subseteq I_u$ is mandatory.
		\item If some vertex $u\in E$ has its weight in $I_m$, then $m$ is also mandatory.
	\end{itemize}
\end{itemize}
The union of the mandatory vertices of all hyperedges then gives the set of all mandatory vertices.
\end{proof}

\input{appLBs_vcb.tex}

\input{appStrict2stage.tex}

\subsection{The vertex split operation}
\label{app:vertexSplit}%
Lemma~\ref{lemma_opt_partitioning} allows us to partition
the vertex set $V$ of a hypergraph orientation instance
$H=(V,E)$
into parts, in such a way that
the expected optimal query cost can be lower-bounded by
the sum of the expected optimal query costs in each
parts. Each part inherits the probability for a
set of vertices to be the set of mandatory vertices in
the part from the original instance. Sometimes we
also need to consider partitions where a single
vertex can be split into fractions that are placed
in different parts of the partition.
In order to do so, we aim to create an instance $H'$ with query costs~$c'$ that is created from $H$ by splitting vertices into fractions and satisfies $\EX[\ensuremath{\mathrm{OPT}}'] = \EX[\ensuremath{\mathrm{OPT}}]$, where $\ensuremath{\mathrm{OPT}}'$ is the optimal query cost for instance $H'=(V',E')$.
In a first step, we consider the vertex cover instance $\bar{G}=(\bar{V},\bar{E})$.
Iteratively, we can replace the original vertices by copies:
We pick a vertex $v \in \bar{V}$ and replace it by multiple copies $v'_1,\ldots, v'_l$ with $c_v = \sum_{i=1}^l c'_{v'_i}$ such that there is an edge between a copy $v'_i$ and a vertex $u \in \bar{V} \setminus \{v\}$ if and only if $\{v,u\} \in \bar{E}$.
Clearly, the weight of the minimum vertex cover for the vertex cover instance remains the same.
Note that we cannot directly modify the vertex cover instance, instead we have to create hyperedges in $H'$ such that $H'$ has the described vertex cover instance.
For the described modifications, this is clearly possible.

For each $M \subseteq V$ let $M'$ be the set of copies created for vertices in $M$.
Let $p'(M')$ be the probability that $M'$ is the set of mandatory vertices for instance $H'$.
If we have $p(M) = p'(M')$ for each $M \subseteq V$, and $p'(S) = 0$ for each subset $S$ that is not the set of copies for some $M \subseteq V$, then it follows
\begin{align*}
\EX[\ensuremath{\mathrm{OPT}}] &= \sum_{M\subseteq V} p(M) \cdot c(M)  + \sum_{M\subseteq V}  p(M) \cdot c(VC_M)\\
&= \sum_{M\subseteq V'} p'(M) \cdot c'(M)  +  \sum_{M\subseteq V'}  p'(M) \cdot c'(VC'_{M}) = \EX[\ensuremath{\mathrm{OPT}}'],
\end{align*}
where $VC'_{M}$ is the minimum weight vertex cover for the subgraph  $\bar{G}'[V'\setminus M]$ of the vertex cover instance of $H'$.
In general, we cannot just set $p'(M)$ arbitrarily, since it depends on the structure of the given hypergraph and the distributions of the corresponding intervals.
However, since we use $\EX[\ensuremath{\mathrm{OPT}}']$ exclusively to lower bound $\EX[\ensuremath{\mathrm{OPT}}]$, we just consider the artificial generalized version of the graph orientation problem, where $p(M)$ for each $M \subseteq V$ is part of the input and can be freely set.
Then, we can create the described instance with $\EX[\ensuremath{\mathrm{OPT}}]=\EX[\ensuremath{\mathrm{OPT}}']$ and compare our algorithm against the optimal cost of the created instance for the generalized graph orientation problem.
Note that the construction of $p'$ implies $p_v = p'_{v'}$ where $v \in V$ is an original vertex and $v'$ is a copy of $v$ in $H'$.

\obsvertexsplitting*


\subsection{Lower bound for strict two-stage algorithms for minimum}
\label{app:strict2stage}

An algorithm $ALG$ is a \emph{strict two-stage algorithm} if in a first stage it non-adaptively queries a set of elements $U_1$ and in a second stage it non-adaptively queries a set of elements $U_2$.
The choice of $U_2$ can depend on the outcome of the queries for~$U_1$.
The algorithm must guarantee that after the second stage it can determine
the minimum weight element.

\begin{theorem}
No strict two-stage algorithm can have competitive ratio
$o(\log n)$ for the hypergraph orientation problem, even
for a single hyperedge with uniform query costs.
\end{theorem}

\begin{proof}
Consider the following instance:
\begin{itemize}
\item $I_1=(1,n+1)$
\item $I_i=(i,n+2)$ for $2\le i\le n$
\end{itemize}
The probability distributions are such that, for each interval $(a,b)$,
the probability is $1/2$ for the weight to be in $(a,a+1)$, and
$1/2$ for the weight to be in $(b-1,b)$. So the weight of each interval
is either at its left end or at its right end, and each of these events happens with probability~$1/2$.

If we query the intervals in order of left endpoint, we
are done as soon as one interval has its weight at its left end.
So each interval has probability $1/2$ to be the last one
we need to query, and the expected number of queries is~$2$.
So $\EX[\ensuremath{\mathrm{OPT}}]\le 2$.

Now consider an arbitrary strict two-stage algorithm $ALG$.
Assume that the algorithm queries $k$ intervals in the
first stage.

Consider the event $E$ that each of the intervals
queried by $ALG$ in the first stage has its weight at the
right end. The event $E$ occurs with probability $1/2^k$
and, if it occurs, the algorithm must query all $n-k$
remaining intervals in the second stage. (Otherwise,
it could happen that all queries in the second stage
also yield a weight at the right end of the queried
interval, and then it is impossible to decide whether an unqueried
element is the minimum or not.)
So the expected cost of $ALG$ is
$$
\EX[ALG] = k + \frac{1}{2^k} (n-k) = \frac{n}{2^k} + k\left(1-\frac{1}{2^k}\right)
$$
If $k\ge \frac12 \log n$, the term $k(1-1/2^k)$ is $\Omega(\log n)$.
If $k < \frac12 \log n$, the term $n/2^k$ is $\Omega(\sqrt{n})$.
So in any case $\EX[ALG]=\Omega(\log n)$ while $\EX[\ensuremath{\mathrm{OPT}}]\le 2$.
\end{proof}

\subsection{Proof of Theorem~\ref{thm:threshold} for arbitrary query costs}
\label{app:threshold_arbitrary_costs}


\textsc{Threshold}\xspace can also handle the graph orientation problem with arbitrary query costs.
In contrast to the uniform problem variant, the algorithm solves a weighted version of~\eqref{eq:threshold:LP}, and a weighted vertex cover problem in Line~\ref{line:threshold_solvevc}. 
In both instances, the query costs are used as weights.

\theoremThreshold*

\begin{proof}
We show that the analysis of Section~\ref{sec:threshold-algorithm} can be generalized for arbitrary query costs.
The expected cost of $\textsc{Threshold}\xspace$ is
\begin{align*}
\EX[ALG] &= c(Q) + \sum_{v\in V\setminus Q} c_v \cdot p_v\\
&= c(M) + c(V_1) + c(VC') + \sum_{v \in V_0} c_v \cdot p_v + \sum_{v \in V_{1/2} \setminus VC'} c_v \cdot p_v.
\end{align*}
Analogously to the analysis of \textsc{Threshold}\xspace for uniform query costs, we compare $\EX[ALG]$ and $\EX[\ensuremath{\mathrm{OPT}}]$ component-wise.
Remember that $\EX[\ensuremath{\mathrm{OPT}}]$ is characterized by Equation~\eqref{eq:LBonOPT}.
The bounds in Equations~\eqref{gt_eq_2} and~\eqref{gt_eq_5} regarding $\EX[\ensuremath{\mathrm{OPT}}_M]$ and $c(M)$, and $\EX[\ensuremath{\mathrm{OPT}}_{V_{1/2}}]$ and $c(VC') + \sum_{v \in V_{1/2} \setminus VC'} c_v \cdot p_v$, respectively, can be generalized straightforwardly using arguments analogous to those in Section~\ref{sec:threshold-algorithm}.
Generalizing Equation~\eqref{gt_eq_4} requires more effort.
	
Compare $c(S) + \sum_{v \in V_0} c_v \cdot p_v$ and $\EX[\ensuremath{\mathrm{OPT}}_{V_1 \cup V_0}]$. 
According to Lemma~\ref{lemma:LP_preprocessing_bipartite}, $V_1$ is a minimum weighted vertex cover for the bipartite graph $G'[V_1\cup V_0]$ that is created by removing all edges within the partitions $V_1$ and $V_0$ from the subgraph induced by $V_1 \cup V_0$.
In contrast to Section~\ref{sec:threshold-algorithm}, we cannot apply the  K\H{o}nig-Egerv\'{a}ry theorem for unweighted vertex covers.
Instead, the theorem gives us a function $\pi:E \rightarrow \mathbb{R}$ with $\sum_{\{u,v\} \in E} \pi(u,v) \le c_v$ for each $v \in V_1 \cup V_0$.
By duality theory, the constraint is tight for each $v \in V_1$, and $\pi(u,v) = 0$ holds if both $u$ and $v$ are in $V_1$. 
Thus, we can interpret $\pi$ as a function that distributes the complete weight $c_v$ of each $v \in V_1$ to the neighbors of $v$ outside of $V_1$.
For each $v \in V_0$ let $\tau_{v}$ denote the fraction of $c_v$ that is not used by $\pi$ to cover the weight of any $v\in V_1$, i.e., $\tau_v = c_v - \sum_{\{u, v\} \in E} \pi(u, v)$.
We can rewrite $c(V_1) + c(V_0)$ as
$$
	\sum_{v\in V_1} \left(c_v + \sum_{u\in V_0} \pi(u,v) \cdot p_v \right) + \sum_{v\in V_0} \tau_v \cdot p_v.
$$
Instead of comparing this expression to $\EX[\ensuremath{\mathrm{OPT}}_{V_1 \cup V_0}]$, we use Observation~\ref{obs:vertex_splitting} to split each $u \in V_0$ into copies $u'_v$ with query cost $c'_{u'_v} = \pi(u,v)$ for each $v \in V_1$ with $\pi(u,v) > 0$, and, if $\tau_u > 0$, in an additional copy $u'$ with query cost $c'_{u'} = \tau_u$. 
We assume that the mandatory probability of each copy is equal to the mandatory probability of the original.
Let $\ensuremath{\mathrm{OPT}}'_{V_1 \cup V'_0}$ denote random variable of Definition~\ref{def:partial_opt} for the modified instance, where $V'_0$ refers to the set of copies of vertices in $V_0$.
Then, according to Observation~\ref{obs:vertex_splitting}, $\EX[\ensuremath{\mathrm{OPT}}_{V_1 \cup V_0}] = \EX[\ensuremath{\mathrm{OPT}}'_{V_1 \cup V'_0}]$.
For each $v\in V_1$, let $H'_v = \{u'_v \mid u \in V_0 \land \pi(u,v) > 0\}$ be the set of copies that cover $c_v$ according to $\pi$.
Further let $\mathcal{H}' = \bigcup_{v\in V_1} H'_v$.
Using Lemma~\ref{lemma_opt_partitioning}, we further partition $\EX[\ensuremath{\mathrm{OPT}}'_{V_1 \cup V'_0}]$ and obtain
$$
	\EX[\ensuremath{\mathrm{OPT}}'_{S \cup D'}] \ge \sum_{v \in S}  \EX[\ensuremath{\mathrm{OPT}}'_{\{v\}\cup H'_v}] + \sum_{u' \in V'_0 \setminus \mathcal{H'}} \EX[\ensuremath{\mathrm{OPT}}'_{\{u'\}}].
$$
For each $s \in S$, the subgraph of the vertex cover instance induced by $\{v\}\cup H'_v$ is a star with a minimum weighted vertex cover of weight $c_v$ and thus 
$$
		\EX[\ensuremath{\mathrm{OPT}}'_{\{v\}\cup H'_v}] \ge c_v.
$$
Each $u' \in V'_0 \setminus \mathcal{H'}$ is a copy of some $u \in V_0$ with $\tau_u > 0$, and has cost $c'_{u'} = \tau_u$.
Since $\ensuremath{\mathrm{OPT}}'_{u'}$ must query $u'$ if it is mandatory, we have 
$$
		\EX[\ensuremath{\mathrm{OPT}}'_{V_1 \cup V'_0}] \ge c(V_1) + \sum_{u \in V'_0 \setminus \mathcal{H'}} \tau_u \cdot p_u.
$$
Finally, by putting the inequalities together, we get
\begin{align*}
		&c(S) + \sum_{v \in V_0} c_v \cdot p_v \\
		 \le &\sum_{v\in V_1} \left(c_v + \sum_{u\in V_0} \pi(u,v)\cdot d \right) + \sum_{v\in V_0} \tau_v \cdot p_v \\
		 \le &  \sum_{v\in V_1} (1+d) \cdot c_v + \sum_{v\in V_0} \tau_v \cdot p_v\\
		 \le &  \sum_{v\in V_1} (1+d) \cdot \EX[\ensuremath{\mathrm{OPT}}'_{\{v\}\cup H'_v}] + \sum_{u' \in V'_0 \setminus \mathcal{H'}} \tau_{u} \cdot p_u\\
		 \le& (1+d) \cdot \EX[\ensuremath{\mathrm{OPT}}'_{V_1 \cup V'_0}] = (1+d) \cdot \EX[\ensuremath{\mathrm{OPT}}_{V_1 \cup V_0}].
\end{align*}

The rest of the analysis follows the same pattern as Section~\ref{sec:threshold-algorithm}.
\end{proof}

\subsection{Auxiliary lemma for the proof of Theorem~\ref{thm:threshold}}
\label{appThresholdBipartiteLemma}

\begin{restatable}[]{lemma}{lemmaLPPreprocessingBipartite}
	\label{lemma:LP_preprocessing_bipartite}
	Let $x^*$ be a half-integral optimal solution to the vertex cover LP relaxation, and let $V_1 = \{v \in V \mid x^*_v = 1\}$ and  $V_0 = \{v \in V \mid x^*_v = 0\}$.
	Then $V_1$ is a minimum-weight vertex cover for the bipartite graph $G'_{V_1\cup V_0}$ that is created from $G[V_1\cup V_0]$ by removing all edges within the partitions $V_1$ and $V_0$.
\end{restatable}

\begin{proof}
	We claim that $V_1$ is a minimum weighted vertex cover for $G'_{V_1\cup V_0}$.
	Assume otherwise; then there is a vertex cover $VC^*$ for $G'_{V_1 \cup V_0}$ with $c(VC^*) < c(V_1)$. 
	Let $R_1 = V_1 \setminus VC^*$ and let $A_0 = V_0 \cap VC^*$, then $VC^* = (V_1 \setminus R_1) \cup A_0$.
	Since $c(VC^*) < c(V_1)$, we get $c(R_1)>c(A_0)$.
	We define a solution $x'$ for the LP Relaxation of Step 4 as follows:
	$$
	x'_v = \begin{cases}
	x'_v = \frac{1}{2} & \text{if } v \in R_1 \cup A_0\\
	x'_v = x^*_v & \text{otherwise}.
	\end{cases}
	$$
	The objective value $c(x')$ of $x'$ is $c(x') = c(x^*) - \frac{1}{2} \cdot c(R_1) + \frac{1}{2} c(A_0)$, where $c(x^*)$ is the objective value of $x^*$.
	Since $c(R_1)>c(A_0)$, we get $c(x') < c(x^*)$.
	We argue that $x'$ is feasible for the LP relaxation, which contradicts the optimality of $x^*$.
	
	All edges that are only incident to elements of $V_{1/2} = V \setminus ({V_1 \cup V_0})$ are still covered, because the values of the corresponding variables were not changed.
	Each edge between some $u \in V_{1/2}$ and some $v \in V_1$ is still covered because $x'_u = \frac{1}{2}$ and $x'_v \ge \frac{1}{2}$ hold by definition of $x'$.
	Edges between elements of $V_1$ are covered for the same reason.
	Since there are no edges between elements of $V_0$, it remains to consider an edge between some $u \in V_0$ and some $v \in V_1$.
	If $v \in V_1 \cap VC^*$, then $x_v' = 1$, and the edge is covered.
	If $v \in V_1 \setminus VC^* = R_1$, then $u \in A_0$ follows because $VC^*$ is a vertex cover for $G'_{V_1 \cup V_0}$.
	By definition of $x'$, it follows $x'_v = \frac{1}{2}$ and $x_u' = \frac{1}{2}$, and, therefore, the edge is covered.
	It follows that $x'$ is feasible, which contradicts the optimality of $x^*$.
	Thus, $V_1$ is a minimum weighted vertex cover for $G'_{V_1 \cup V_0}$.
\end{proof}


\subsection{Tightness proof for the analysis of \textsc{Threshold}\xspace}
\label{appThreshold_tightness}

\begin{theorem}	
	The analysis of {\em \textsc{Threshold}\xspace} is tight.
	More precisely, there is no threshold $d\in (0,1]$ such that 
	its competitive ratio is less than the Golden ratio $\phi=(1+\sqrt{5})/2$.
\end{theorem}


\begin{proof}
	Consider the Threshold algorithm with some threshold $d\in (0,1]$. We give two instances of the graph orientation problem with uniform query cost and show that the algorithm has either a competitive ratio of at least $1+d-\epsilon$, for an arbitrarily small $\epsilon > 0$ (in particular, $\epsilon < d$), or at least $1/d$. This implies the lower bound.
	
	As the first instance, consider a single edge $\{u,v\}$ and mandatory probabilities $p_u=d-\epsilon$ and $p_v=0$.
	Threshold finds a basic feasible solution for the vertex cover LP relaxation for the edge $\{u,v\}$, say $x^{\textup{LP}}_u=0$ and $x^{\textup{LP}}_v=1$. It queries $v$, and then it still has to query $u$ with probability $p_u=d-\epsilon$, while it would have been sufficient to query only~$u$. The algorithm's competitive ratio is at least $1+d-\epsilon$.
	
	As a second instance, consider a star with the center $v$ and $n$ edges $\{v,u_i\}$ for $i\in\{1,2,\ldots,n\}$. Let $p_v=1$ and $p_{u_i}=d$. Then the algorithm queries all $v$ and $u_i$ due to the threshold $d$, whereas it would have been sufficient to query $v$ first and then continue with querying $u_i$ only if needed, that is, with probability $\EX[X_{u_i}]=d$ for each $i$. The algorithm has cost $n+1$, while the optimal cost is at most $1+n\cdot d$. Thus, the competitive ratio is at least $(n+1)/(1+n\cdot d)$, which tends to $1/d$ for $n\rightarrow \infty$.	
\end{proof}

\subsection{Applying the threshold algorithm to special cases}
\label{app:constant}

The threshold algorithm of Section~\ref{sec:threshold} requires an $\alpha$-approximation for a vertex cover problem.
In this section, we discuss further special cases for which \textsc{Threshold}\xspace can be applied with a polynomial running time. 
We show the following theorem.

\theoConstantSets*
We separately show the results for orienting $\mathcal{O}(\log \ |V|)$ hyperedges and sorting $\mathcal{O}(1)$ sets.

\paragraph*{Orienting $\mathcal{O}(\log \ |V|)$ hyperedges}  

Consider the problem of orienting a hypergraph $H=(V,E)$ with $|E| \le k$ for some $k \in \mathcal{O}(\log \ |V|)$.
In order to apply the threshold algorithm, we have to solve the minimum vertex cover problem for a subgraph of the vertex cover instance $\bar{G}$ of $H$.
Note that even in this special case, the number edges and vertices in $\bar{G}$ can be arbitrarily large.

\begin{theorem}
	Given a hypergraph orientation instance $H=(V,E)$ with $|E| \le k$ for some $k \in \mathcal{O}(\log \ |V|)$, a minimum weight vertex cover for $\bar{G}$ of $H$ can be computed in polynomial time. 
	Thus, for $\epsilon,\delta > 0$, \textsc{Threshold}\xspace is $1.618+\epsilon$-competitive with probability at least $1-\delta$.
\end{theorem}

\begin{proof}
	It only remains to show that the minimum weight vertex cover for $\bar{G}$ can be computed in polynomial time. Then, Theorem~\ref{theorem_threshold_hyper} implies the theorem.
	
	By definition of $\bar{G}$, for each hyperedge $F$, a vertex cover must contain either the left-most element $v_1$ of $F$ or all elements of $F\setminus \{v_1\}$.
	Thus, when computing a vertex cover, we, for each hyperedge $F$, have to decide whether to include $v_1$ or $F \setminus \{v_1\}$.
	The running time of enumerating through all such vertex covers is $\mathcal{O}(2^k)$, which is polynomial for $k \in \mathcal{O}(\log \ |V|)$.
\end{proof}



\paragraph*{Orienting the union of a constant number of interval graphs}
Consider the problem of orienting a graph $G=(V,E)$ with $E = \bigcup_{i=1}^k E_i$, where $G_i=(V_i,E_i)$ with $V_i \subseteq V$, for $1 \le i \le k$, is an interval graph.
Orienting such an $G_i$ corresponds to the problem of sorting a single set of uncertainty intervals.
Thus, orienting $G=(V,E)$ corresponds to the problem of sorting $k$ (possibly overlapping) sets.
In the following, we assume that $k$ is constant, and show the following theorem.

\begin{theorem}
	\label{theo_sorting_constant}
	A modified version of \textsc{Threshold}\xspace with polynomial running time is $1.618$-competitive for the problem of orienting a graph $G=(V,E)$ with $E = \bigcup_{i=1}^k E_i$, where $G_i=(V_i,E_i)$ with $V_i \subseteq V$, for $1 \le i \le k$, is an interval graph and $k$ is constant.
\end{theorem}

Since we assume preprocessed instances, i.e., $I_{v_1} \not\subseteq I_{v_2}$ holds for each edge $\{v_1,v_2\}$, it follows that each $G_i$ is a proper interval graph.

In order to use the threshold algorithm for this special case, we employ Algorithm~\ref{alg:clique_removal}, which uses a local ratio technique to remove all cliques $C$ of size $|C| \ge  3$ from $G$.

\begin{algorithm}[htb]
	\KwIn{Instance $G=(V,E)$ with query costs $c_v$ for each $v \in V$}
	Initialize $Q = \emptyset$\;
	\While{$G$ contains a clique $C$ with $|C| \ge 3$}{
		Let $\delta = \min_{v\in C} c_v$\;
		Set $c_v = c_v - \delta$ for each $v \in C$\label{Line_clique_reduction}\;
		Set $Q = Q \cup \{v \mid v\in C \land c_v = 0 \}$ and $V = V \setminus Q$\;		
	}
	\Return The modified $G$, the modified query costs $c_v$, and query set $Q$\;
	\caption{Clique removal}
	\label{alg:clique_removal}
\end{algorithm}

After applying this algorithm, each $G_i$ is a proper interval graph without cliques of size at least $3$, and, thus, triangle-free.

\begin{lemma}
	\label{lemma_vc_constant_width}
	Let $G=(V,E)$ be a graph orientation instance with $E = \bigcup_{i=1}^k E_i$, where $G_i=(V_i,E_i)$, for $1 \le i \le k$, with $V_i \subseteq V$ is a proper and triangle-free interval graph and $k$ is constant. Then, a minimum weight vertex cover of $G$ can be computed in polynomial time.
\end{lemma}

Before we prove the lemma, we use it to show that the clique removal allows us to solve the special case in polynomial time using the following algorithm:

\begin{enumerate}
	\item Execute Algorithm~\ref{alg:clique_removal} to obtain a modified graph $G$, modified query costs $c_v$, and a query set $Q_P$.
	\item Execute \textsc{Threshold}\xspace on the modified instance, add $Q_p$ to the query set $Q$ that is queried in Line~\ref{line:threshold_stage1} of \textsc{Threshold}\xspace.
	Use Lemma~\ref{lemma_vc_constant_width} as black box for the vertex cover problem.
\end{enumerate}

\begin{proof}[Proof of Theorem~\ref{theo_sorting_constant}]
	We show that this algorithm is $1.618$-competitive for the considered special case.
	Since Lemma~\ref{lemma_vc_constant_width} allows us to optimally solve the vertex cover problem,  we can apply Theorem~\ref{thm:threshold} with $\alpha=1$ to conclude that \textsc{Threshold}\xspace is $1.618$-competitive on the modified instance in Step~$2$ of the algorithm.
	
	Thus, it remains to argue about the cost for querying $Q_P$.
	Let $i$ be an iteration of the while-loop of Algorithm~\ref{alg:clique_removal}, let $C_i$ denote the clique that is considered in this iteration, and let $\delta_i$ denote the value $\delta$ of this iteration. 
	The cost for querying $Q_P$ is bounded by $c(Q_P) \le \sum_i |C_i| \cdot \delta_i$.
	Since $\ensuremath{\mathrm{OPT}}$ must query at least $|C_i|-1$ elements of each clique (cf.~Lemma~\ref{lemma:witness_set}), the reduction of the query costs in Line~\ref{Line_clique_reduction} reduces the cost of $\ensuremath{\mathrm{OPT}}$ by at least $(|C_i|-1)\cdot \delta_i$.
	Since this holds for each realization, $\EX[\ensuremath{\mathrm{OPT}}]$ is reduced by at least this amount as well.
	Let $\EX[\ensuremath{\mathrm{OPT}}_r]$ denote the expected reduction in the query cost of $\EX[\ensuremath{\mathrm{OPT}}]$ caused by the clique removal, then $\EX[\ensuremath{\mathrm{OPT}}_r] \ge \sum_i (|C_i|-1) \cdot \delta_i$.
	Thus, we can charge $c(Q_p)$ against $\EX[\ensuremath{\mathrm{OPT}}_r]$ to derive 
	$$
	\frac{c(Q_P)}{\EX[\ensuremath{\mathrm{OPT}}_r]} \le \max_i \left\{\frac{|C_i|}{(|C_i|-1)}\right\} \le \frac{3}{2},
	$$
	where the last inequality follows from $|C_i| \ge 3$.
	We can conclude that the algorithm is $\max\{1.5,\ 1.618\} = 1.618$-competitive.
\end{proof}


\paragraph*{Proof of Lemma~\ref{lemma_vc_constant_width}}

Let $G=(V,E)$ be a graph orientation instance with $E = \bigcup_{i=1}^k E_i$, where $G_i=(V_i,E_i)$, for $1 \le i \le k$, with $V_i \subseteq V$ is a proper and triangle-free interval graph and $k$ is constant.
Each $G_i$ being a proper and triangle-free interval graph implies that $G_i$ is the union of a set of disjoint paths.
Furthermore, since we assume preprocessed instances, i.e., $I_{v_1} \not\subseteq I_{v_1}$ for each edge $\{v_1,v_2\}$, the lower limits of the uncertainty intervals of each $G_i$ define a unique total order $\prec_i$ of the vertices in $V_i$.

We compute a minimum weight vertex cover via a dynamic program.
A \emph{state} $u$ of the dynamic program is a tuple $u=(P,S)$, where $P$ contains a single vertex $v_i$ for each $G_i$, and $S_{v_i}$ assigns each $v_i\in P$ to either $0$ or $1$.
The state $u$ represents a partial vertex cover for the sub graph induced by the vertices $v_i$ and all vertices that are before $v_i$ in the corresponding order $\prec_i$. 
The value $S_{v_i}$ denotes whether $v_i$ is part of the represented vertex cover ($S_{v_i}=1$) or not ($S_{v_i}=0$). 
We introduce two dummy vertices $s$ and $t$ with cost of zero, and add them to each $G_i$ as the first and last element of the order $\prec_i$.
Without loss of generality, we assume that $s$ and $t$ are part of every vertex cover.
We define $u_0 = (\{s\},1)$ as the initial state, representing that $s$ is part of every vertex cover.
Further, $u_f = (\{t\},1)$ represents a terminal state.
Since the number of subgraphs $G_i$ is bounded by $k$, the number of states is bounded by $\mathcal{O}(n^k \cdot 2^k)$.

We define a directed state graph $G' = (U,A,w)$, where $U$ is the set of DP states, such that the weight of the shortest $u_0$-$u_f$-path in $G'$ corresponds to the weight of a minimum weight vertex cover of $G$.
Consider a state $u=(P,S)$.
Let $v$ be a vertex, such that, for each $G_i$ with $v \in V_i$, the direct predecessor of $v$ according to $\prec_i$ is contained in $P$.
Note that, if $u\not= u_f$, such a vertex $v$ always exists.
Let $B \subseteq P$ denote the set of those predecessors, and 
let $B' = \{v' \in B \mid \{v',v\} \in E\}$ denote the subset of $B$ containing only vertices that share an edge with $v$.	
We add an arc $a$ between $u=(P,S)$ and $u'=(P',S')$ if the following holds:
\begin{enumerate}
	\item 
	If $S_{v'} = 1$ holds for all $v' \in B'$, we add an edge to $u'$ if $P' = \{ v' \in P \mid \exists 1\le i \le k: v' \in V_i \land v \not\in V_i\} \cup \{v\}$,
	 $S'_{v'} = S_{v'}$ for all $v' \in P \cap P'$, and $S'_{v} \in \{0,1\}$. 
	Intuitively, this arc models the extension of the partial vertex cover represented by $u$ by either adding $v$ to the partial vertex cover or deciding that $v$ is not part of the extended partial vertex cover.
	By definition, in the subproblem modeled by $u'$, the vertex $v$ only shares edges with elements of $B'$.
	In case $S_{v'} = 1$ holds for all $v' \in B'$, all elements of $B'$ are part of the vertex cover represented by $u$.
	Thus, in state $u'$, all vertices that share edges with $v$ are already part of the vertex cover, and vertex $v$ can therefore either be part of the represented vertex cover or not, in both cases the partial vertex cover is feasible.
	\item 
	If there exists an $v' \in B'$ with $S_{v'} = 0$, we additionally require $S'_{v}=1$. 
	In this case, $v$ shares an edge with a vertex $v'$ in the sub graph of $u'$, such that $v'$ is not part of the corresponding vertex cover. 
	Thus, $v$ must be part of the vertex cover.
\end{enumerate}
If $S'_v = 1$, we set $w_a = c_v$, which represents that the cost of the vertex cover increased by adding $v$.
Otherwise, we set $w_a = 0$.

A straightforward induction on the construction implies the following:
There is a vertex cover of $G$ with weight $C$ if and only if there is a $u_0$-$u_f$-path with cost $C$ in $G'$.
Since the number of states is bounded by $\mathcal{O}(n^k \cdot 2^k)$, we can find the shortest $u_0$-$u_f$-path with a running time exponential in $k$ but polynomial in the rest of the input.
This implies Lemma~\ref{lemma_vc_constant_width}.















 










\subsection{The graph orientation problem on a special weighted star}
\label{subsec:star:subproblem}

\begin{restatable}[]{lemma}{VertexCoverWeightedStar}
	\label{lemma:vertex_cover_weigthed_star}
	Consider the problem of orienting a star $G=(V,E)$  with center $v \in V$. 
	Let $L$ and $R$ be the vertex cover-based algorithms that query $VC_1 = \{v\}$ and $VC_2 = V\setminus\{v\}$ in the first stage, respectively.
	If $\EX[L] = \EX[R]$, then $L$ is $\frac{4}{3}$-competitive.	
\end{restatable}

\begin{proof}
The analysis relies on $p_v$ and $p_u$ being independent for each $u \in H_v$. 
In the graph orientation problem, for every vertex $u$ the probability $p_u$ corresponds to the probability that the exact value of at least one $v$ with $\{u,v\} \in E$ is contained in $I_u$. 
Since the graph is bipartite and there is an edge between $v$ and $u$, it follows that $v$ and $u$ do not share any adjacent vertices.
Thus, $p_v$ and $p_{u}$ are independent.
This also implies that $p_v$ and~$L$ are independent.
In the following let $H_v = V \setminus \{v\}$ denote the set of leaves. 
Thus, for the expected costs of the algorithms, we have
\begin{equation}
\EX[L] = c_v + \sum_{u\in V} p_u \cdot c_u = p_v \cdot c_v + c(H_v) = \EX[R].
\label{eq:LRdef}
\end{equation}

For each $v \in V$, let $X_v$ be an indicator variable denoting whether $v$ is mandatory.
Note that $p_v =\mathbb{P}[X_v=1]$.

\subparagraph{Case $c(H_v) \le c_v$.}
\label{subsubsec:star:assumption}

If $c(H_v) \le c_v$, querying the leaves is always the best strategy if the center is not mandatory, i.e., if $X_v = 0$, independently of whether the elements of $H_v$ are mandatory.
Similarly, if the center is mandatory, i.e., if $X_v = 1$, querying the center first is always the best strategy.
Thus, we can write $\EX[\ensuremath{\mathrm{OPT}}]$ as
\begin{align*}
	\EX[\ensuremath{\mathrm{OPT}}] &= p_v \cdot \EX[L \mid X_v = 1] + (1-p_v) \cdot \EX[R \mid X_v = 0]\\
	 &= p_v \cdot \EX[L] + (1-p_v) \cdot c(H_v)\\
	&= p_v \cdot \EX[L] + (1-p_v) \cdot (\EX[L] - p_v \cdot c_v)\\
	&\le \EX[L] - p_v \cdot (1-p_v) \cdot c_v,
\end{align*}
where the second equality uses the fact that $p_v$ and $L$ are independent, and the third equality uses $\EX[L] = \EX[R]$.
Since $0 \le p_v \le 1$, it follows that $p_v \cdot (1-p_v) \cdot c_v \le \frac{c_v}{4}$.
This directly implies $\frac{\EX[L]}{\EX[\ensuremath{\mathrm{OPT}}]} \le \frac{\EX[L]}{\EX[L] - p_v \cdot (1-p_v) \cdot c_v} \le \frac{4}{3}$, where the last inequality uses $\EX[L] \ge c_v$.
For the remainder of the analysis, we assume $c(H_v) > c_v$.


\subparagraph{Characterizing $\EX[L]$ and $\EX[\ensuremath{\mathrm{OPT}}]$.}

We begin by characterizing $\EX[L]$ in terms of conditional expectations:
$$
\EX[L] = p_v \cdot \EX[L \mid X_v = 1] + (1-p_v) \cdot \EX[L \mid X_v = 0].
$$
Since $X_v$ and $L$ are independent, it follows that $\EX[L \mid X_v = 1] = \EX[L]$.
If the center is mandatory, i.e., $X_v = 1$, we know that both $\ensuremath{\mathrm{OPT}}$ and $L$ have the same expected value.
That is, $\EX[\ensuremath{\mathrm{OPT}} \mid X_v = 1] = \EX[L \mid X_v = 1]$.

Thus, we are more interested in the case when $X_v = 0$.
For this case, we know that
$$\EX[L \mid X_v = 0] = \EX[L] =  c_v + \sum_{u\in H_v} p_u \cdot c_u = \EX[R] = p_v \cdot c_v + c(H_v).$$
But whether algorithm $L$ is the best possible strategy depends on how much query cost of the leaves is mandatory.
We have two cases.
In the first case, when $\sum_{u \in H_v} (1-X_u) \cdot  c_u \ge c_v$, querying the center first is a better strategy than querying the leaves first, even if the center is not mandatory.
In the second case, when $\sum_{u \in H_v} (1-X_u) \cdot c_u < c_v$, querying the leaves is the better strategy if additionally $X_v = 0$.

Consider the case when $\sum_{u \in H_v} (1-X_u) \cdot c_u \ge c_v$.
In this case, the cost of algorithm~$L$ is at most $c(H_v)$ and we can write $\EX[L \mid X_v = 0 \land c(H_v) \cdot (1-X_u) \ge c_v] = c(H_v) - s$, where $s \ge 0$ describes the slack between $c(H_v)$ and $\EX[L \mid X_v = 0 \land \sum_{u \in H_v} (1-X_u) \cdot c_u \ge c_v]$.
Define $q_L := \mathbb{P}\left[\sum_{u \in H_v} (1-X_u) \cdot c_u\ge c_v\right]$; then we have
\begin{align*}
\EX[L \mid X_v = 0] = q_L  \cdot \left(c(H_v) - s\right) + (1-q_L) \cdot \EX\Big[L \Big| X_v = 0 \land \sum_{u \in H_v} (1-X_u)  \cdot c_u< c_v\Big].
\end{align*}
Using this equation and $\EX[L \mid X_v = 0] = \EX[L] = \EX[R] = p_v \cdot c_v + c(H_v)$, we can derive
\begin{align*}
\EX\Big[L \Big| X_v = 0 \land \sum_{u \in H_v} (1-X_u) \cdot c_u < c_v\Big] = c(H_v) + \frac{1}{1-q_L} \cdot p_v \cdot c_v + \frac{q_L}{1-q_L} \cdot s.
\end{align*}
Finally, we use this to characterize $\EX[L]$:
\begin{align*}
	\EX[L] &= p_v \cdot \EX[L] + (1-p_v) \cdot q_L \cdot \left(c(H_v) - s\right)\\
	&+ (1-p_v) \cdot (1-q_L) \cdot \left(c(H_v) + \frac{1}{1-q_L} \cdot p_v \cdot c_v + \frac{q_L}{1-q_L} \cdot s\right)
\end{align*}

To characterize $\EX[\ensuremath{\mathrm{OPT}}]$, observe that the only case where $\ensuremath{\mathrm{OPT}}$ and $L$ deviate is the case where $X_v = 0$ and $\sum_{u \in H_v} (1-X_u) \cdot c_u < c_v$.
For that case, $\ensuremath{\mathrm{OPT}}$ queries only the leaves at cost $c(H_v)$.
Thus, we can write $\EX[\ensuremath{\mathrm{OPT}}]$ as
$$\EX[\ensuremath{\mathrm{OPT}}] = p_v \cdot \EX[L] + (1-p_v) \cdot q_L \cdot \left(c(H_v) - s\right) + (1-p_v) \cdot (1-q_L) \cdot c(H_v).$$

\subparagraph{Upper bounding the competitive ratio.}

We now use the characterizations of $\EX[L]$ and $\EX[\ensuremath{\mathrm{OPT}}]$ to show $\frac{4}{3}$-competitiveness.
Consider the difference between $\EX[L]$ and $\EX[\ensuremath{\mathrm{OPT}}]$,
$$
\EX[L] - \EX[\ensuremath{\mathrm{OPT}}] = (1-p_v) \cdot (p_v \cdot c_v + q_L \cdot s).
$$
We can use this difference to upper bound the competitive ratio:
$$
\frac{\EX[L]}{\EX[\ensuremath{\mathrm{OPT}}]} \le \frac{\EX[L]}{\EX[L]- (1-p_v) \cdot p_v \cdot c_v - (1-p_v) \cdot q_L \cdot s}.
$$

We continue by upper bounding $q_L \cdot s$.
Consider again the characterization of $\EX[L]$.
In the case when $X_v = 0$ and $\sum_{v\in H_v} (1-X_u) \cdot c_u < c_v$, the expected value of $L$ is larger than $c(H_v)$  by $\frac{1}{(1-q_L)} \cdot p_v \cdot c_v + \frac{q_L}{1-q_L} \cdot s$.
By Equation~(\ref{eq:LRdef}), the difference between $c(H_v)$ and the cost of $L$ is at most $c_v$.
It follows that
\begin{align*}
&\frac{1}{(1-q_L)} \cdot p_v \cdot c_v + \frac{q_L}{1-q_L} \cdot s \le c_v\\
\implies& p_v \cdot c_v + q_L \cdot s \le c_v \cdot (1 - q_L)\\
\implies& q_L \cdot s \le c_v \cdot (1-p_v) - c_v \cdot q_L \\
\implies& q_L \cdot (c_v + s) \le c_v \cdot (1-p_v)\\
\implies& q_L  \le c_v \cdot \frac{1-p_v}{c_v + s}
\end{align*}
Thus, we obtain 
$$
\frac{\EX[L]}{\EX[\ensuremath{\mathrm{OPT}}]} \le \frac{\EX[L]}{\EX[L]- (1-p_v) \cdot p_v \cdot c(v) - \frac{c_v \cdot (1-p_v)^2 \cdot s}{c_v+s}}.
$$
Moreover, we can observe that this upper bound decreases for increasing $\EX[L]$, so we only need a lower bound on $\EX[L]$.
In the characterization of $\EX[L]$, the expected cost of~$L$ for the case when $X_v = 0$ and $c(H_v) \cdot (1-p_u) \ge c_v$ is $c(H_v) - s$. 
Since the cost of $L$ can never be smaller than $c_v$, it follows that $s \le c(H_v) - c_v$, so the expected cost of the algorithm is $\EX[L] = \EX[R] = c(H_v) + c_v \cdot p_v \ge c_v + s + p_v \cdot c_v$.
By plugging this into the ratio we obtain:
\begin{align*}
\frac{\EX[L]}{\EX[\ensuremath{\mathrm{OPT}}]} &\le \frac{c_v + p_v \cdot c_v+ s}{c_v + p_v \cdot c_v + s -(1-p_v) \cdot p_v \cdot c_v - \frac{c_v \cdot (1-p_v)^2 \cdot s}{c_v+s}}\\
&= \frac{c_v + p_v \cdot c_v + s}{c_v + p_v \cdot c_v + s - (1 - p_v) \cdot p_v \cdot c_v - \frac{c_v \cdot (1-p_v)^2 \cdot s}{c_v+s}}
\end{align*}
We can now use  
$$\frac{c_v \cdot (1-p_v)^2 \cdot s}{c_v+s} = \frac{c_v \cdot (1-p_v)^2 \cdot s}{c_v \cdot (1+\frac{s}{c_v})} = \frac{(1-p_v)^2 \cdot s}{1+\frac{s}{c_v}}$$
to write the ratio as
\begin{align*}
\frac{\EX[L]}{\EX[\ensuremath{\mathrm{OPT}}]} &\le \frac{c_v + c_v \cdot p_v + s}{c_v + p_v \cdot c_v + s - (1 -p_v) \cdot p_v \cdot c_v - \frac{(1-p_v)^2 \cdot s}{1+\frac{s}{c_v}}}\\
&= \frac{1 + p_v + \frac{s}{c_v}}{1 + p_v + \frac{s}{c_v} - (1 - p_v) \cdot p_v - \frac{(1-p_v)^2 \cdot \frac{s}{c_v}}{1+\frac{s}{c_v}}}
\end{align*}
Assume $c_v > 0$; we can do this w.l.o.g.\ because we can query free elements in a preprocessing step. Let $s' = \frac{s}{c_v}$; then we have that 
\begin{align*}
\frac{\EX[L]}{\EX[\ensuremath{\mathrm{OPT}}]} 
&\le \frac{1 + p_v + s'}{1 + p_v + s' - (1 - p_v) \cdot p_v - \frac{(1-p_v)^2 \cdot s'}{1+s'}} = f(p_v, s').
\end{align*}

\subparagraph{Showing $\frac{4}{3}$-competitiveness.} To complete the proof, we show that $f(p_v, s') \leq \frac{4}{3}$ for any $0 \le p_v \le 1$ and $s' \ge 0$.
We can rewrite
\begin{displaymath}
 f(p_v, s') = \frac{(1 + s')(1 + p_v + s')}{1 + s' + (p_v + s')^2}.
\end{displaymath}
We fix the value of~$s'$ and look for critical points, so we consider the partial derivative of $f(p_v, s')$ on $p_v$, which is
\begin{displaymath}
 \frac{\partial}{\partial p_v} f(p_v, s') = - \frac{(1 + s')(p_v^2 + 2 p_v (1 + s') + s'^2 + s' - 1)}{((p_v + s')^2 + 1 + s')^2}.
\end{displaymath}
The denominator is clearly always greater than zero.

First let us consider $s' \geq \frac{1}{\phi} = \frac{\sqrt{5}-1}{2}$.
If $s'^2 + s' - 1 \geq 0$, which always holds for $s' \geq \frac{1}{\phi}$, then clearly $\displaystyle\frac{\partial}{\partial p_v} f(p_v, s') \leq 0$, so $f(p_v, s')$ is non-increasing and is maximized when $p_v = 0$.
Let $g(s') = f(0, s') = \displaystyle\frac{(1+s')^2}{1 + s' + s'^2}$; then $\displaystyle\frac{d}{ds'} g(s') = \displaystyle\frac{1-s'^2}{(1+s'+s'^2)^2}$, and the only critical point is obtained by taking $\displaystyle \frac{d}{ds'} g(s') = 0$, which holds when $s' = 1$.
It is clear that $\displaystyle \frac{d}{ds'} g(s') \geq 0$ for $0 \leq s' \leq 1$ and $\displaystyle \frac{d}{ds'} g(s') \leq 0$ for $s' \geq 1$, so $g(s')$ has a global maximum when $s' = 1$.
Thus the maximum value of $f(p_v, s')$ for $s' \geq \frac{1}{\phi}$ and $p_v \geq 0$ is $f(0, 1) = \frac{4}{3}$.

Now assume $0 \leq s' < \frac{1}{\phi}$.
Let us look at the critical points by taking $\displaystyle\frac{\partial}{\partial p_v} f(p_v, s') = 0$.
Since the denominator is always positive and $s' \geq 0$, we only have a zero when
\begin{displaymath}
  N(p_v, s') = p_v^2 + 2 p_v (1 + s') + s'^2 + s' - 1 = 0, 
\end{displaymath}
which by the quadratic formula yields $p_v = -1 -s' \pm \sqrt{s' + 2}$.
Since we need $p_v \geq 0$, we have $p_v = -1 -s' + \sqrt{s' + 2}$, and $0 \leq p_v \leq 1$ since $0 \leq s' < \frac{1}{\phi}$.
We claim that this is always a maximum point.
Clearly $\displaystyle\frac{\partial}{\partial p_v} f(p_v, s') \geq 0$ whenever $N(p_v, s') \leq 0$ and vice-versa, but $\displaystyle\frac{\partial}{\partial p_v} N(p_v, s') = 2(1 + p_v + s')$, which is non-negative for $p_v, s' \geq 0$, so $N(p_v, s')$ is non-decreasing.
We can thus conclude that $\displaystyle\frac{\partial}{\partial p_v} f(p_v, s') \geq 0$ for $0 \leq p_v \leq -1 -s' + \sqrt{s' + 2}$ and $\displaystyle\frac{\partial}{\partial p_v} f(p_v, s') \leq 0$ for $-1 -s' + \sqrt{s' + 2} \leq p_v \leq 1$, so we have a maximum point when $p_v = -1 - s' + \sqrt{s' + 2}$.
Finally, let 
\begin{displaymath}
 h(s') = f(-1 -s' + \sqrt{s'+2}, s') = \frac{(1 + s')\sqrt{s' + 2}}{2s' + 4 -2 \sqrt{s' + 2}};
\end{displaymath}
we have that $\displaystyle\frac{d}{ds'} h(s') = \frac{1}{4 \sqrt{s' + 2}}$, which is always non-negative for $s' \geq 0$.
Thus $h(s')$ is a non-decreasing function, so its maximum for $0 \leq s' < \frac{1}{\phi}$ is attained when $s'$ tends to $\frac{1}{\phi}$.
Therefore, for $0 \leq s' < \frac{1}{\phi}$ and $p_v \geq 0$, we have that $f(p_v, s') \leq h(\frac{1}{\phi}) = \frac{\sqrt{5}+3}{4} < \frac{4}{3}$.
\end{proof}

\subsection{Proof of Theorem~\ref{thm:VC-single-set}}
\label{subsec:proof-vc-single-set}

\theoremVCSingleSet*

\begin{proof}
Let $S= \{v_0,v_1,\ldots,v_n\}$ be the single hyperedge.
We assume that $v_0,v_1,\ldots,v_n$ are ordered by non-decreasing 
left endpoints of the corresponding intervals $I_0,\ldots,I_n$.
That is, $v_0$ is the leftmost vertex of $S$ and,
by our assumptions in Section~\ref{sec:preliminaries}, 
all intervals $I_1,\ldots,I_n$ intersect $I_0$, 
but none of them is contained in $I_0$.

In this setting, the vertex cover instance is a star with center $v_0$
and leaves $v_1,\ldots,v_n$.
Thus, we only have to consider two vertex cover-based algorithms:
the algorithm $L$ that queries vertex cover $\{v_0\}$ in the first stage, 
and the algorithm $R$ that queries $\{v_1,\ldots,v_n\}$ in the first stage.
Note that, while the vertex cover instance is a star, we cannot apply the analysis of Appendix~\ref{subsec:star:subproblem}:
This is because that analysis requires the mandatory probabilities of $v_0$ and each $v_i$ with $1 \le i \le n$ to be independent, which is not the case here.

If $n\ge 3$, it is sufficient to consider algorithm $L$.
The algorithm simply queries the vertices in order of
left endpoints, starting with $v_0$, until we can identify
the minimum element. 
If $v_0$ is also queried by $\ensuremath{\mathrm{OPT}}$,
we have $L=\ensuremath{\mathrm{OPT}}$. Otherwise, $\ensuremath{\mathrm{OPT}}$ must query all
of $v_1,\ldots,v_n$, and the competitive ratio is at most
$\frac{n+1}{n} \le \frac{4}{3}$.
Since $L$ is $\frac{4}{3}$-competitive in this case, so is \textsc{BestVC}\xspace.

So it remains to consider the cases $n=1$ and $n=2$.
For $n=1$, the configuration of the intervals is shown in Figure~\ref{fig:min1set2}.
Here, $p$ is the probability that the weight of $v_0$ is contained in~$I_1$, and $q$ is the probability that the weight of $v_1$ is contained in $I_0$. 
Note that in this case $p$ and $q$ correspond to the mandatory probabilities of $v_1$ and $v_0$.

\begin{figure}[h]
  \centering
  \begin{tikzpicture}[line width = 0.3mm, scale=1.2]
    \interval{$I_0$}{0}{2}{0}
    \interval{$I_1$}{1}{3}{-0.5}

    \draw[dotted] (1, 0.5) -- (1, -1);
    \draw[dotted] (2, 0.5) -- (2, -1);

    \node at (0.5, 0.2) {$1-p$};
    \node at (1.5, 0.18) {$p$};

    \node at (1.5, -0.32) {$q$};
    \node at (2.5, -0.3) {$1-q$};
  \end{tikzpicture}
  \caption{Configuration for a hyperedge with two vertices.}
  \label{fig:min1set2}
\end{figure}

We can assume that $q\ge p$ (otherwise, we swap $I_0$ and $I_1$ and flip the x-axis). Since $\ensuremath{\mathrm{OPT}}$ has to query at least one vertex and only queries a second one if both are mandatory, we have $\E[\ensuremath{\mathrm{OPT}}]=1+pq$.
Algorithm $L$ queries $I_0$ first and has $\E[L]=(1-p)\cdot 1+ p \cdot2 = 1+p$. The ratio $\displaystyle\frac{1+p}{1+pq}$ for $0\le p\le 1$ and $p\le q\le 1$ is maximized for $q=p$, in which case it is $\displaystyle\frac{1+p}{1+p^2}$.
The derivative of $f(p)=\displaystyle\frac{1+p}{1+p^2}$ is $f'(p)=\displaystyle\frac{1-2p-p^2}{(1+p^2)^2}$, which is positive for $0\le p< -1+\sqrt{2}$, equal to $0$ for $p=-1+\sqrt{2}$, and negative for $1+\sqrt{2}<p\le 1$.
Hence, the maximum of $f(p)$ in the range $0\le p\le 1$ is attained at $p_0=-1+\sqrt{2}\approx 0.4142$
with value $f(p_0)=\frac{1+\sqrt{2}}{2}\approx 1.207$.
Thus, 
\textsc{BestVC}\xspace is $1.207$-competitive for $n=1$.

It remains to consider case $n=2$. The configuration of the intervals is shown in Figure~\ref{fig:min1set3}.
Note that the order of the right endpoints of $I_1$ and $I_2$ is irrelevant for the proof.

\begin{figure}[h]
  \centering
  \begin{tikzpicture}[line width = 0.3mm, scale=1.2]
    \interval{$I_0$}{0}{3}{0}
    \interval{$I_1$}{1}{4}{-0.5}
    \interval{$I_2$}{2}{5}{-1}

    \draw[dotted] (1, 0.5) -- (1, -1.5);
    \draw[dotted] (2, 0.5) -- (2, -1.5);
    \draw[dotted] (3, 0.5) -- (3, -1.5);

    \node at (0.5, 0.2) {$p_0$};
    \node at (1.5, 0.2) {$p_1$};
    \node at (2.5, 0.2) {$p_2$};

    \node at (1.5, -0.3) {$q_1$};
    \node at (2.5, -0.3) {$q_2$};
    \node at (3.5, -0.3) {$q_3$};

    \node at (2.5, -0.8) {$r_2$};
    \node at (4, -0.8) {$r_3$};
  \end{tikzpicture}
  \caption{Configuration for three intervals.}
  \label{fig:min1set3}
\end{figure}

Again, we only have to consider the two vertex cover-based algorithms $L$ and $R$. 
We have:
\begin{eqnarray*}
\E[\ensuremath{\mathrm{OPT}}] &=& p_0 \cdot 1 + p_1 \cdot 2 + p_2 (q_1 \cdot 2 + q_2\cdot 3+q_3(r_2\cdot 3+r_3 \cdot 2))\\
\E[L] &=& p_0\cdot 1 + p_1\cdot 2 + p_2(q_1\cdot2+q_2\cdot3+q_3\cdot3)\\
\E[R] & = & 3-q_3 r_3
\end{eqnarray*}
By definition, 
\textsc{BestVC}\xspace has an expected value of at most $\min\{ \E[L], \E[R] \}$, and, thus, the competitive ratio is at most
$$
\frac{\min\{ \E[L], \E[R] \}}{\E[\ensuremath{\mathrm{OPT}}]}.
$$

First, we want to remove some parameters to simplify our calculations.
Note that if we move $\varepsilon$ probability from $q_2$ to $q_1$,
then $\E[\ensuremath{\mathrm{OPT}}]$ and $\E[L]$ decrease by $p_2\varepsilon$, while $\E[R]$ is unchanged. So we can assume that $q_2=0$.
Furthermore, if we move $\varepsilon$ probability fro $p_1$ to~$p_0$,
then $\E[\ensuremath{\mathrm{OPT}}]$ and $\E[L]$ decrease by $\varepsilon$, while $\E[R]$ is unchanged. So we can assume that $p_1=0$.
This gives:
\begin{eqnarray*}
\E[\ensuremath{\mathrm{OPT}}] &=& p_0 \cdot 1 + p_2 (q_1 \cdot 2 + q_3(r_2\cdot 3+r_3 \cdot 2))\\
\E[L] &=& p_0\cdot 1 + p_2(q_1\cdot2+q_3\cdot3)\\
\E[R] & = & 3-q_3 r_3
\end{eqnarray*}
Now we rename the parameters as
\begin{displaymath}
p := p_2, \quad 1 - p = p_0, \quad q := q_1, \quad 1-q = q_3, \quad r := r_2, \quad 1-r = r_3.
\end{displaymath}
The equations then become:
\begin{eqnarray*}
\E[\ensuremath{\mathrm{OPT}}] &=& 1+p+p(1-q)r\\
\E[L] &=& 1+p(2-q)\\
\E[R] & = & 2+r+q-qr
\end{eqnarray*}

The corresponding picture is shown in Figure~\ref{fig:min1set3renamed}.

\begin{figure}[h]
  \centering
  \begin{tikzpicture}[line width = 0.3mm, scale=1.2]
    \interval{$I_0$}{0}{3}{0}
    \interval{$I_1$}{1}{4}{-0.5}
    \interval{$I_2$}{2}{5}{-1}

    \draw[dotted] (1, 0.5) -- (1, -1.5);
    \draw[dotted] (2, 0.5) -- (2, -1.5);
    \draw[dotted] (3, 0.5) -- (3, -1.5);

    \node at (0.5, 0.2) {$1-p$};
    \node at (1.5, 0.2) {$0$};
    \node at (2.5, 0.2) {$p$};

    \node at (1.5, -0.3) {$q$};
    \node at (2.5, -0.3) {$0$};
    \node at (3.5, -0.3) {$1-q$};

    \node at (2.5, -0.8) {$r$};
    \node at (4, -0.8) {$1-r$};
  \end{tikzpicture}
  \caption{Configuration for three intervals assuming $p_1 = q_2 = 0$.}
  \label{fig:min1set3renamed}
\end{figure}

\paragraph*{Case 1: $\E[L] \le \E[R]$.}
We want to show:
\begin{equation}
\E[L] \le \frac43 \cdot \E[\ensuremath{\mathrm{OPT}}]
\label{case1claim}
\end{equation}
This inequality (\ref{case1claim}) can be transformed as follows:
\begin{eqnarray*}
3+3p(2-q) &\le& 4+4p+4p(1-q)r \\
\Leftrightarrow
2p+4pqr & \le &1+4pr+3pq
\end{eqnarray*}
This is clearly satisfied for $p=0$, so we can divide by $p$ and get:
\begin{eqnarray}
2+4qr & \le & \frac1p +4r+3q
\label{case1claimB}
\end{eqnarray}
With respect to $p$, this inequality is most difficult to satisfy
if $p$ is as large as possible. To see how large $p$ can be, we
look back at our assumption for the current case,
$\E[L] \le \E[R]$.
Expanding this assumption gives:
$$
1+p(2-q) \le 2+r+q-qr
$$
This can be reformulated as:
\begin{equation}
p \le \frac{1+r+q-qr}{2-q} \label{condp}
\end{equation}
We now distinguish two cases depending on whether the right-hand side of (\ref{condp}) is larger than~$1$ or not.

\paragraph*{Case 1.1: $\displaystyle\frac{1+r+q-qr}{2-q}\ge 1$.}
This condition is equivalent to:
\begin{eqnarray}
1+r+q-qr & \ge & 2-q \nonumber \\
\Leftrightarrow r+2q & \ge & 1+qr \label{cond11}
\end{eqnarray}
In this case, we can set $p$ to $1$. Instead of inequality (\ref{case1claimB}), it now suffices to
show the following:
\begin{eqnarray}
2+4qr & \le & 1 +4r+3q \nonumber \\
\Leftrightarrow
1+4qr & \le & 4r+3q \label{case1claimC}
\end{eqnarray}
By (\ref{cond11}) we have:
$$
1+4qr = 1+qr + 3qr \le r+2q+3qr
$$
Thus, to show (\ref{case1claimC}) it suffices to show:
\begin{eqnarray*}
r+2q+3qr & \le & 4r+3q \\
\Leftrightarrow 3qr & \le & 3r+q
\end{eqnarray*}
This is obviously satisfied as $3qr\le 3r$ follows from $q\le 1$.

\paragraph*{Case 1.2: $\displaystyle\frac{1+r+q-qr}{2-q}< 1$.}
This condition is equivalent to:
\begin{eqnarray}
1+r+q-qr & < & 2-q \nonumber \\
\Leftrightarrow
r+2q & < & 1+qr \nonumber \\
\Rightarrow
4qr+4q^2r^2 & > & 4r^2q + 8 rq^2 \label{cond12}
\end{eqnarray}
(In the last step, we have multiplied the inequality with $4qr$.)
In this case, we can set $p$ to $\displaystyle\frac{1+r+q-qr}{2-q}$.
Instead of inequality (\ref{case1claimB}) it now suffices to show the following:
\begin{eqnarray*}
2+4qr & \le & \frac{2-q}{1+r+q-qr} +4r+3q \\
\Leftrightarrow
(1+r+q-qr)(2+4qr-4r-3q) & \le & 2-q \\
\Leftrightarrow
2-2r-q-5qr-4r^2-3q^2+7q^2r+8qr^2-4q^2r^2
 & \le & 2-q \\
\Leftrightarrow
7q^2r+8qr^2 & \le & 2r+qr+4r^2+3q^2+(4q^2r^2+4qr)
\end{eqnarray*}
By (\ref{cond12}), it suffices to show that:
$$
7q^2r+8qr^2  \le  2r+qr+4r^2+3q^2+4r^2q+8rq^2
$$
This can be transformed into:
$$
4qr^2 \le 2r+qr+4r^2+3q^2+rq^2
$$
This clearly holds because $4qr^2\le 4r^2$ follows from $q\le 1$.

\paragraph*{Case 2: $\E[L] \ge \E[R]$.}
We want to show:
\begin{equation}
\E[R] \le \frac43 \cdot \E[\ensuremath{\mathrm{OPT}}]
\label{case2claim}
\end{equation}
This inequality (\ref{case2claim}) can be transformed as follows:
\begin{eqnarray}
6+3r+3q-3qr &\le& 4+4p+4p(1-q)r \nonumber \\
\Leftrightarrow
2+3r+3q+4pqr & \le & 3qr+4p+4pr \nonumber \\
\Leftrightarrow
p(4+4r-4qr) & \ge & 2+3r+3q-3qr
\label{case2claimB}
\end{eqnarray}
Expanding our assumption
$\E[L] \ge \E[R]$
gives:
$$
2+r+q-qr \le 1+p(2-q)
$$
This can be reformulated as:
\begin{eqnarray}
1+r+q+pq & \le & 2p+qr \nonumber \\
\Leftrightarrow
p(2-q) & \ge & 1+r+q-qr \nonumber \\
\Leftrightarrow
p & \ge & \frac{1+r+q-qr}{2-q}
\label{cond2}
\end{eqnarray}
We observe that this is only possible if the right-hand side of (\ref{cond2}) is at most~$1$, so we
must have the following for this to be possible, but we will not need to use this fact in the
remainder of the proof.
\begin{eqnarray}
1+r+q-qr &\le& 2-q \nonumber\\
r+2q &\le& 1+qr \nonumber
\end{eqnarray}
Inequality (\ref{case2claimB}) is most difficult to satisfy if $p$ is as
small as possible, so in view of (\ref{cond2}) we can set $p=\displaystyle\frac{1+r+q-qr}{2-q}$
and then prove the following inequality to establish~(\ref{case2claimB}):
\begin{eqnarray}
\frac{1+r+q-qr}{2-q}(4+4r-4qr) & \ge & 2+3r+3q-3qr \nonumber \\
\Leftrightarrow
2r+5qr+4r^2+3q^2+4q^2r^2 & \ge & 8qr^2+7q^2r \label{case2claimC}
\end{eqnarray}
We show that (\ref{case2claimC}) holds by showing the following two inequalities:
\begin{eqnarray}
5qr+4r^2 &\ge& 8qr^2 \label{case2claimD1}\\
2r+3q^2+4q^2r^2 &\ge&7q^2r \label{case2claimD2}
\end{eqnarray}
Inequality (\ref{case2claimD1}) holds because $5qr\ge 5qr^2$ and $4r^2\ge 4qr^2$, so
$5qr+4r^2\ge 9qr^2\ge 8qr^2$.
To show (\ref{case2claimD2}), we distinguish two cases for~$r$.

\paragraph*{Case 2.1: $r\le \frac35$.}
In this case $3q^2 \ge 5 q^2r$ and hence
$2r+3q^2 \ge 2q^2r + 5 q^2r = 7q^2r$, and thus (\ref{case2claimD2}) holds.

\paragraph*{Case 2.2: $r > \frac35$.}
In this case we have $4q^2r^2\ge 4q^2r \cdot \frac{3}{5}\ge 2 q^2r$,
and hence $2r+3q^2+4q^2r^2 \ge 2q^2r+3q^2r+2q^2r=7q^2r$, so (\ref{case2claimD2}) also
holds in this case.
\end{proof}

\section{Introduction}
\label{sec:intro}
\input{secIntro.tex}

\section{Definitions and preliminary results}
\label{sec:preliminaries}

\input{secLBonOPT.tex}

\section{A threshold algorithm for orienting hypergraphs}
\label{sec:threshold}

We present an algorithm for orienting graphs and its generalization
to hypergraphs.

\input{secThresholdAlg}

\section{Vertex cover-based algorithms: improved results for special cases}
\label{sec:VC-alg}

\input{secVC-intro.tex}
\input{secVC-Alg-graph-orientation.tex}
\input{secVC-Alg-single-set.tex}


\section{Conclusion}
\label{sec:conclusion}

In this paper, we present algorithms for the (hyper)graph orientation problem under stochastic explorable uncertainty.
It remains open to determine the competitive ratio of \textsc{BestVC}\xspace for the general (hyper)graph orientation problem, and to investigate how the algorithm behaves if it has to rely on an $\alpha$-approximation to solve the vertex cover subproblem.
In this context, one can consider the resulting algorithm as a standalone algorithm, or as a subroutine for \textsc{Threshold}\xspace.
Our analysis suggests that, to achieve a competitive ratio better than~$1.5$, algorithms have to employ more adaptivity; exploiting this possibility remains an open problem.  
Finally, it would be interesting to characterize the vertex cover instances arising in our \textsc{Threshold}\xspace algorithm. In addition to the relevance from a combinatorial point of view, such a characterization may allow an improved $\alpha$-approximation algorithm for those instances.





\subsection{Orienting graphs}
\label{sec:threshold-algorithm}

{We consider the graph orientation problem.} 
{As a subproblem,}
we solve a 
vertex cover problem. 
{This problem is NP-hard and $2$-approximation algorithms are known \cite{yannakakis_edge_1980}.} For several special graph classes, there are improved algorithms \cite{halperin2002improved}. Using an $\alpha$-approximation 
as a black box, we give a competitive ratio 
between $\phi \approx 1.618$ ($\alpha = 1$) and $2$ ($\alpha = 2$)
as a function depending on $\alpha$.
{Appendix~\ref{app:thres} contains a figure showing the competitive ratio in dependence on $\alpha$.}

\begin{algorithm}[htb]
	\KwIn{Instance $G=(V,E)$, $p_v$ for each $v \in V$, parameter $d \in [0,1]$, \\\phantom{\textbf{Input:\:}}and an $\alpha$-approximation black box for the vertex cover problem}
	Let $M = \{v \in V \mid p_v \ge d\}$\label{line:threshold_addM}\;
	Solve~\eqref{eq:threshold:LP} for $G[V \setminus M]$ and let $x^*$ be an optimal basic feasible solution\label{Line:threshold_LP}\;
	Let $V_1 = \{v \in V \mid x^*_v = 1\}$ and similarly $V_{1/2},V_0$ \label{line:threshold_defV}\;
	Use the $\alpha$-approximation black box to approximate a vertex cover $VC'$ for $G[V_{1/2}]$\label{line:threshold_solvevc}\;
	Query $Q = M \cup V_1 \cup VC'$\label{line:threshold_stage1}\tcc*[l]{$Q$ is a vertex cover}
	Query the mandatory elements of $V \setminus Q$ \label{line:threshold_stage2}\; 
	\caption{\textsc{Threshold}\xspace}
	\label{alg:threshold}
\end{algorithm}

Algorithm~\ref{alg:threshold} is parameterized by a threshold $d\in [0,1]$, which is optimized depending on the approximation ratio $\alpha$ of the chosen vertex cover procedure.
The algorithm executes a preprocessing of the vertex cover instance by using the following classical LP relaxation, {for which each optimal basic feasible solution is half-integral}~\cite{nemhauser1975}: 
\begin{equation}\tag{LP}\label{eq:threshold:LP}
\begin{array}{lll}
\min &\sum_{v\in V} c_v\cdot x_v\\
\text{s.t. }& x_v + x_u \ge 1 & \forall \{u,v\} \in E\\
& x_v \ge 0& \forall v \in V
\end{array}
\end{equation}

\begin{restatable}[]{theorem}{theoremThreshold}
	\label{thm:threshold}
	Given an $\alpha$-approximation with $1\le\alpha\le 2$ for the vertex cover problem
	(on the induced subgraph $G[V_{1/2}]$, see Line~\ref{line:threshold_solvevc}),
	\emph{\textsc{Threshold}\xspace} with parameter $d$ achieves a competitive ratio of $\max\{\frac{1}{d}, \alpha + (2-\alpha) \cdot d \}$ {for the graph orientation problem.}
	Optimizing~$d$ yields a competitive ratio of $\frac{1}{2}(\alpha + \sqrt{8 - \alpha(4 - \alpha)})$.
\end{restatable}

\begin{proof}
Here, we show the result for uniform query costs. 
The generalization to arbitrary query costs requires an additional technical step involving vertex splitting and is discussed in Appendix~\ref{app:threshold_arbitrary_costs}. 
Since $Q$ is a vertex cover for $G$, querying it in Line~\ref{line:threshold_stage1} and 
resolving all remaining dependencies in Line~\ref{line:threshold_stage2} clearly solves the graph orientation~problem.
Note that $V\setminus Q$ is an independent set in~$G$, and thus the nodes in $V\setminus Q$
can only be made mandatory by the results of the queries to~$Q$. Hence, it is known after
Line~\ref{line:threshold_stage1} which nodes in $V\setminus Q$ are mandatory, and they
can be queried in Line~\ref{line:threshold_stage2} in arbitrary order (or in parallel).

	We continue by showing the competitive ratio of $\max\{\frac{1}{d}, \alpha + (2-\alpha) \cdot d \}$.
	Algebraic transformations show that the  optimal choice for the threshold is $d(\alpha)= 2/(\alpha+\sqrt{8-\alpha(4-\alpha)})$. The desired competitive ratio for \textsc{Threshold}\xspace with $d=d(\alpha)$ follows.

	The algorithm queries set $Q$ and all other vertices only if they are mandatory, hence
	\begin{equation}\label{eq_thres_alg}
			\EX[ALG] = |Q| + \sum_{v\in V\setminus Q} p_v 
					= |M| + |V_1| + |VC'| + \sum_{v \in V_0} p_v + \sum_{v \in V_{1/2} \setminus VC'} p_v.
	\end{equation}
	The expected optimal cost can be lower bounded by partitioning and Lemma~\ref{lemma_opt_partitioning}:
	\begin{equation}
	\EX[\ensuremath{\mathrm{OPT}}] \ge  \EX[\ensuremath{\mathrm{OPT}}_{M}] + \EX[\ensuremath{\mathrm{OPT}}_{V_1 \cup V_0}] + \EX[\ensuremath{\mathrm{OPT}}_{V_{1/2}}].
	\label{eq:LBonOPT}
	\end{equation}
	In the remainder we compare $\EX[ALG]$ with $\EX[\ensuremath{\mathrm{OPT}}]$ component-wise.

	We can lower bound $\EX[\ensuremath{\mathrm{OPT}}_M]$ by $\sum_{v\in M} p_v$ using Equation~\eqref{eq_opt_partitioning_1}.
	By definition of~$M$, it holds that $\EX[\ensuremath{\mathrm{OPT}}_M] \ge \sum_{v \in M} p_v \ge d \cdot |M|$. Thus,
	\begin{equation}\label{gt_eq_2}
		|M| \le \frac{1}{d} \cdot \EX[\ensuremath{\mathrm{OPT}}_M].
	\end{equation}

	Next, we compare $|V_1| + \sum_{v \in V_0} p_v$ with $\EX[\ensuremath{\mathrm{OPT}}_{V_1 \cup V_0}]$.
	For this purpose, let $G[V_1 \cup V_0]$ be the subgraph of $G$ induced by $V_1 \cup V_0$,
	and let $G'[V_1 \cup V_0]$ be the bipartite graph that is created by removing all edges between elements of $V_1$ from $G[V_1\cup V_0]$.
	It follows from similar arguments as in~\cite[Theorem~2]{nemhauser1975} that $V_1$ is a minimum vertex cover of $G'[V_1\cup V_0]$. 
	(See
	Appendix~\ref{appThresholdBipartiteLemma}.)
	This allows us to apply the famous K\H{o}nig-Egerv\'{a}ry theorem~\cite{SchrijverBook}.
	By the latter there is a matching $h$ mapping each $v \in V_1$ to a distinct $h(v) \in V_0$ with $\{v,h(v)\} \in E$.
	Denoting $S = \{h(v) \mid v \in V_1 \}$, we can infer $\EX[\ensuremath{\mathrm{OPT}}_{V_1 \cup V_0}] \ge \EX[\ensuremath{\mathrm{OPT}}_{V_1 \cup S}] + \EX[\ensuremath{\mathrm{OPT}}_{V_0 \setminus S}]$.
			  
	Any feasible solution must query at least one endpoint of all edges of the form $\{v,h(v)\}$.
	This implies $\EX[\ensuremath{\mathrm{OPT}}_{V_1 \cup S}] \ge |V_1|$.
	Since additionally $p_{h(v)} \le d$ for each $h(v) \in S$, we get
	\begin{equation}\label{gt_eq_3}
		\sum_{v\in V_1} \left( 1 + p_{h(v)} \right) \le (1+d) \cdot |V_1| \le (1+d) \cdot \EX[OPT_{V_1\cup S}].
	\end{equation}
	By lower bounding $\EX[OPT_{V_0\setminus S}]$ with $\sum_{v\in V_0\setminus S} p_v$ and using \eqref{gt_eq_3}, we get
	\begin{align}\label{gt_eq_4}
			|V_1| + \sum_{v \in V_0} p_v & =  \sum_{v\in V_1} \left(1 + p_{h(v)}\right) + \sum_{v\in V_0\setminus S} p_v\\
			& \le (1+d) \cdot \EX[\ensuremath{\mathrm{OPT}}_{V_1\cup S}] + \EX[\ensuremath{\mathrm{OPT}}_{V_0 \setminus S}] 		\notag
			\le  (1+d) \cdot \EX[\ensuremath{\mathrm{OPT}}_{V_1\cup V_0}].								\notag
	\end{align}
	
	Finally, consider the term $|VC'| + \sum_{v \in V_{1/2} \setminus VC'} p_v$. 
	Let $VC^*$ be a minimum cardinality vertex cover for $G[V_{1/2}]$.
	Then, it holds $|VC^*| \ge \frac{1}{2} \cdot |V_{1/2}|$.
	This is, because in the optimal basic feasible solution to the LP relaxation $x^*$,  
	each vertex in $V_{1/2}$ has a value of $\frac{1}{2}$.
	A vertex cover with $|VC^*| < \frac{1}{2} \cdot |V_{1/2}| $ would contradict the optimality of $x^*$.
	{The following part of the analysis crucially relies on $|VC^*| \ge \frac{1}{2} \cdot |V_{1/2}| $, which is the reason why \textsc{Threshold}\xspace executes the LP relaxation-based preprocessing before applying the $\alpha$-approximation.}
			  
	Now, the expected cost of the algorithm for the subgraph $G[V_{1/2}]$ is $|VC'| + \sum_{v\in I'} p_v \le |VC'| + d\cdot |I'|$ with $I' = V_{1/2} \setminus VC'$.
	Since $|VC'| \ge |VC^*| \ge \frac{1}{2} \cdot |V_{1/2}| $, there is a tradeoff between the quality of $|VC'|$ and the additional cost of $d\cdot |I'|$.
	If $|VC'|$ is close to $\frac{1}{2} \cdot |V_{1/2}| $, then it is close to $|VC^*|$ but, on the other hand, $|I'|$ then is close to $\frac{1}{2} \cdot |V_{1/2}| $, which means that the additional cost $d\cdot |I'|$ is high. 
	Vice versa, if the cost for $|VC'|$ is high because it is larger than $\frac{1}{2} \cdot |V_{1/2}| $, then $|I'|$ is close to zero and the additional cost $d\cdot |I'|$ is low.
	We exploit this tradeoff and upper bound $\frac{|VC'| + d\cdot |I'|}{|VC^*|}$ in terms of the approximation factor $\alpha$ of the vertex cover approximation.
	Assume that the approximation factor $\alpha$ is tight, i.e., $|VC'| = \alpha \cdot |VC^*|$.
	Since $d \le 1$, this is the worst case for the ratio $\frac{|VC'| + d\cdot |I'|}{|VC^*|}$.
	(In other words, if the approximation factor was not tight, we
	could replace $\alpha$ by the approximation factor that is actually achieved and carry out the following
	calculations with that smaller value of $\alpha$ instead, yielding an even better bound.)
	Using $|VC'| = \alpha \cdot |VC^*|$ and $|VC^*| \ge \frac{1}{2} \cdot |V_{1/2}| $, we can derive
	\begin{align*}
		|I'| &= |V_{1/2}| - |VC'|
			 = |V_{1/2}| - \alpha \cdot |VC^*| 
			 \le (2-\alpha) \cdot |VC^*|.
	\end{align*}
	For the cost of the algorithm for subgraph $G[V_{1/2}]$ we get
	\begin{align*}
		|VC'| + d\cdot |I'| &\le \alpha \cdot |VC^*| + d \cdot (2-\alpha) \cdot |VC^*|
		= (\alpha + (2-\alpha) \cdot d) \cdot |VC^*|.
	\end{align*}
	Since $|VC^*| \le \EX[\ensuremath{\mathrm{OPT}}_{V_{1/2}}]$, we get
	\begin{equation}\label{gt_eq_5}
		|VC'| + d\cdot |I'| \le (\alpha + (2-\alpha) \cdot d) \cdot \EX[\ensuremath{\mathrm{OPT}}_{V_{1/2}}].
	\end{equation}

	Combining Equations~\eqref{eq_thres_alg},~\eqref{gt_eq_2},~\eqref{gt_eq_4} and~\eqref{gt_eq_5}, we can upper bound the cost of the algorithm:
	\begin{align*}
		\EX[ALG] 
		&= |M| + |V_1| + \sum_{v \in V_0} p_v + |VC'| + \sum_{v \in V_{1/2} \setminus VC'} p_v.\\
		&\le  \frac{1}{d} \cdot \EX[\ensuremath{\mathrm{OPT}}_M] + (1+d) \cdot \EX[\ensuremath{\mathrm{OPT}}_{V_1 \cup V_0}] + (\alpha + (2-\alpha) \cdot d)) \cdot \EX[\ensuremath{\mathrm{OPT}}_{V_{1/2}}]\\
		&\le  \max\left\{\frac{1}{d},(1+d),(\alpha + (2-\alpha) \cdot d)\right\} \cdot \EX[\ensuremath{\mathrm{OPT}}],
	\end{align*}
	where the last inequality follows from the lower bound on $\ensuremath{\mathrm{OPT}}$ in \eqref{eq:LBonOPT}. Observe that for any $d \in [0,1]$ and $\alpha \in [1,2]$, it holds that $(\alpha + (2-\alpha) \cdot d) \ge (1+d)$. {We conclude with 
	$
	\EX[ALG] \le \max\{\frac{1}{d},(\alpha + (2-\alpha) \cdot d)\} \cdot \EX[\ensuremath{\mathrm{OPT}}],
	$
	which implies the theorem.}
\end{proof}


In Appendix~\ref{appThreshold_tightness}, we show that the analysis of \textsc{Threshold}\xspace is tight.
To benefit from a better approximation factor than $\alpha=2$ for solving the minimum vertex cover problem, we would need to know in advance the specialized graph class on which we want to solve this subproblem. 
In some cases, we can benefit from optimal or approximation algorithms{, e.g., using \textsc{Threshold}\xspace with the PTAS for planar graphs~\cite{Bar1982} allows us to achieve a
competitive ratio of at most $1.618 + \epsilon$, for any $\epsilon > 0$, if the input graph is planar.}
\subsection{Orienting hypergraphs}
\label{sec:orienting-hyperedges}
 
\begin{theorem}
	\label{theorem_threshold_hyper}
	Given an $\alpha$-approximation with $1\le\alpha\le 2$ for the vertex cover problem
	(on the induced subgraph $\bar{G}[V_{1/2}]$ of the vertex cover instance given by Definition~\ref{def:vertex_cover_instance}, cf.~Line~\ref{line:threshold_solvevc}),
	a modified version of the \emph{\textsc{Threshold}} algorithm solves the hypergraph orientation problem with arbitrary query costs with competitive ratio
	$$
	R=	
	\frac{1}{2} \left(\alpha + \sqrt{\alpha ^2 + 4 (2-\alpha) (1 + \alpha \epsilon + (2- \alpha)\epsilon^2)} + (4 - 2 \alpha)\epsilon \right)
	$$
	with probability at least $1 - \delta$. Its running time is upper bounded by the complexity of the sampling procedure and the vertex cover black box procedure.
\end{theorem}
\begin{proof}

The modified algorithm works with the vertex cover instance $\bar G$ instead 
of the given hypergraph $H$, following
Definition~\ref{def:vertex_cover_instance}. In Line~\ref{line:threshold_addM},
we use $d(\alpha)=1/R +\epsilon$.
In Line~\ref{line:threshold_stage2}, we iteratively query mandatory vertices
until the instance is solved.
In addition, we use a random estimation
$Y_v$ of $p_v$, instead of the precise probability, using the procedure
described in Lemma~\ref{lem:sampling} with parameters $\epsilon$ and $\delta'$
such that $1- \delta = (1 - \delta')^n$. As a result, with probability at
least $1 - \delta$ we have that for every vertex $v$, the estimation $Y_v$ has
absolute error at most~$\epsilon$.  In case of this event we obtain the
following bound on the cost (which is optimized for the chosen value of $d$), namely $\EX[{\textrm{ALG}}] \leq \max \{\frac1{d- \epsilon}, (1+d  +\epsilon), (\alpha + (2 - \alpha)(d + \epsilon))\}  \cdot \EX[\ensuremath{\mathrm{OPT}}]$.
\end{proof}

Sorting a set of elements is equivalent to determining,
for each pair of elements, which of the two has smaller weight. Hence,
the problem of sorting multiple sets of elements with uncertain weights
is a special case of the graph orientation problem: For each set to be
sorted, the edge set of a complete graph on its elements is added to
a graph, and the resulting instance of the
graph orientation problem is then equivalent to the given instance
of the sorting problem.
In Appendix~\ref{app:constant}, we show the following theorem.
\begin{restatable}{theorem}{theoConstantSets}
	{
 	For the special cases of orienting $\mathcal{O}(\log \ |V|)$ hyperedges and sorting $\mathcal{O}(1)$ sets, \textsc{Threshold}\xspace can be applied with $\alpha = 1$ in polynomial running time.
	}
\end{restatable}


\subsection{A best possible algorithm for orienting bipartite graphs}

\begin{theorem}\label{Theorem:vertex_cover_bipartite}
	\emph{\textsc{BestVC}\xspace} is $\frac{4}{3}$-competitive for the bipartite graph orientation problem.
\end{theorem}

\begin{proof}
In Appendix~\ref{subsec:star:subproblem}, we show that \textsc{BestVC}\xspace is $\frac{4}{3}$-competitive for the problem of orienting stars if both vertex cover-based algorithms (either querying the leaves or the center first) have the same expected cost.
In this proof, we divide the instance into subproblems that fulfill these requirements, and use the result for stars to infer $\frac{4}{3}$-competitiveness for bipartite graphs.

	
Let $VC$ be a minimum-weight vertex cover (with weights $c_v \cdot (1-p_v)$) as computed by \textsc{BestVC}\xspace in the first phase.
By the K\H{o}nig-Egerv\'{a}ry theorem (e.g.,~\cite{SchrijverBook}), there is
a function $\pi:E \rightarrow \mathbb{R}$ with $\sum_{\{u,v\} \in E} \pi(u,v) \le c_v \cdot (1-p_v)$ for each $v \in V$.
By duality theory, 
the constraint is tight for each $v \in VC$, and $\pi(u,v) = 0$ holds if both $u$ and $v$ are in $VC$. 
Thus, we can interpret $\pi$ as a function that distributes the 
weight of each $v \in VC$ to its neighbors outside of $VC$.

For each $v \in VC$ and $u \in V \setminus VC$, let $\lambda_{u,v} := \frac{\pi(u,v)}{(1-p_u) \cdot c_u}$ denote the fraction of the weight of $u$ that is used by $\pi$ to cover the weight of $v$.
Moreover, for $u \in V \setminus VC$, let $\tau_u := 1 - \sum_{\{u, v\} \in E} \lambda_{u,v}$ be the fraction of the weight of $u$ that is not used by $\pi$ to cover the weight of any $v \in VC$.
Then, we can write the expected cost of \textsc{BestVC}\xspace as follows:
\begin{equation}
\EX[\textsc{BestVC}\xspace] = \sum_{v\in VC} \bigg(c_v+\sum_{u\in V\setminus VC} p_u \cdot \lambda_{uv} \cdot c_u \bigg) + \sum_{u\in V\setminus VC} p_u \cdot \tau_u \cdot c_u .
\end{equation}
Using Observation~\ref{obs:vertex_splitting}, we compare $\EX[\textsc{BestVC}\xspace]$ with the expected optimum $\EX[\ensuremath{\mathrm{OPT}}']$ for an instance $G'=(V',E',c')$ that is created by splitting vertices. 
We modify the mandatory distribution as 
in Section~\ref{sec:lower-bounds-on-OPT}, which implies $\EX[\ensuremath{\mathrm{OPT}}] = \EX[\ensuremath{\mathrm{OPT}}']$. 
We add the following copies:
\begin{enumerate}
	\item For each $v \in VC$, we add a copy $v'$ of $v$ to $V'$ with $c'_{v'} = c_v$.
	\item For all $u \in V\setminus VC$ and $v \in VC$ with $\lambda_{u,v} > 0$,
	we add a copy $u_v'$ of $u$ to $V'$ with $c'_{u_v'} = \lambda_{u,v} \cdot c_u$.
	\item For each $u \in V\setminus VC$ with $\tau_u > 0$, we add a copy $u'$ of $u$ to $V'$ with $c'_{u'} = \tau_u \cdot c_u$.
\end{enumerate}
Let $p'_{v}$ denote the probability of $v$ being mandatory for instance $G'$.
By definition of the vertex split operation, we have $p_v = p'_{u}$ for each $v \in V$ and each copy $u \in V'$ of $v$.
Further, for each $v \in VC$, define $H'_v = \{u'_v \mid u \in V \text{ with } \lambda_{u,v} > 0\}$. 
By definition of $H'_v$ and $G'$, all $H'_v$ are pairwise disjoint. 
Let $\mathcal{H}' = \bigcup_{v \in VC} \left(H'_v \cup \{v'\}\right)$; then we can express $\EX[\textsc{BestVC}\xspace]$ as follows:
\begin{align}
\EX[\textsc{BestVC}\xspace] &= \sum_{v\in VC} \bigg(c_v+\sum_{u\in V\setminus VC} p_u \cdot \lambda_{u,v} \cdot c_u \bigg) + \sum_{u\in V\setminus VC} p_u \cdot \tau_u \cdot c_u \nonumber \\
&=  \sum_{v\in VC} \bigg(c'_{v'}+\sum_{u\in H'_v} p_u' \cdot c'_u \bigg) + \sum_{u \in V' \setminus \mathcal{H'}} p'_u \cdot c'_u. \nonumber 
\end{align}
Similarly, we can lower bound $\EX[\ensuremath{\mathrm{OPT}}']$ using Lemma~\ref{lemma_opt_partitioning}:
\begin{equation}\label{eq_vc_opt_lb}
	\smash{
	\EX[\ensuremath{\mathrm{OPT}}'] \ge \hspace*{-0.5ex} \sum_{v\in VC} \EX[\ensuremath{\mathrm{OPT}}'_{H'_v\cup \{v'\}}] + \hspace*{-2ex}\sum_{u \in V' \setminus \mathcal{H'}} \hspace*{-1ex}\EX[\ensuremath{\mathrm{OPT}}'_{\{u\}}]
	\ge  \sum_{v\in VC} \EX[\ensuremath{\mathrm{OPT}}'_{H'_v\cup \{v'\}}] + \hspace*{-2ex} \sum_{u \in V' \setminus \mathcal{H'}} \hspace*{-1ex} p_u' \cdot c'_u.}\hspace*{1.5ex}
\end{equation}
Since the term $\sum_{u \in V' \setminus \mathcal{H'}} p_u' \cdot c'_u$ shows up in both inequalities, it remains, for each $v\in VC$, to bound $c'_{v'}+\sum_{u\in H'_v} p_u' \cdot c'_u$ in terms of  $\EX[\ensuremath{\mathrm{OPT}}'_{H'_v\cup \{v'\}}]$.
By definition of $H'_v$, we have $ (1-p'_{v'}) \cdot c'_{v'} = \sum_{u \in H_v'} (1-p_u') \cdot c'_u$, which implies
\begin{equation}\label{eq_secVC_1}
c'_{v'}+\sum_{u\in H'_v} p'_{u} \cdot c'_u = p'_{v'} \cdot c'_{v'} + \sum_{u\in H'_v} c'_u.
\end{equation}
The value $\EX[\ensuremath{\mathrm{OPT}}'_{H'_v \cup \{v'\}}]$ corresponds to the expected optimum for the subproblem which considers the subgraph induced by $H'_v \cup \{v'\}$ (which is a star), uses $p'_u$ as the mandatory probability for each $u \in H'_v \cup \{v'\}$, and uses $c'_u$ as the query cost of each $u \in H'_v \cup \{v'\}$.
For this subproblem, $c'_{v'}+\sum_{u\in H'_v} p'_{u} \cdot c'_u $ corresponds to the expected cost of the vertex cover-based algorithm that queries vertex cover $\{v'\}$ in the first stage.
Furthermore, $ p'_{v'} \cdot c'_{v'} + \sum_{u\in H'_v} c'_u$ corresponds to the expected cost of the vertex-cover based algorithm that queries vertex cover $H'_v$ in the first stage. 
In summary, we have a star orientation subproblem for which both vertex cover-based algorithms (querying the leaves or the center first) have the same expected cost (cf. Equation~\eqref{eq_secVC_1}).
As a major technical step, we show that \textsc{BestVC}\xspace is $\frac{4}{3}$-competitive for such subproblems, which implies
$$c'_{v'}+\sum_{u\in H'_v} p'_u \cdot c'_u \le \frac{4}{3} \cdot \EX[\ensuremath{\mathrm{OPT}}'_{H'_v \cup \{v'\}}].$$  
A corresponding lemma is proven in \cref{subsec:star:subproblem}.
We remark that the lemma requires $p'_{v'}$ to be independent of each $p'_{u}$ with $u \in  H'_v$; otherwise the subproblem does not correspond to the star orientation problem. 
As the input graph is bipartite, such independence follows by definition.

Using this inequality and Equation~\eqref{eq_vc_opt_lb}, we conclude that \textsc{BestVC}\xspace is $4/3$-competitive.
\begin{align*}
\EX[\textsc{BestVC}\xspace] &= \sum_{v\in VC} \bigg(c'_{v'}+\sum_{u\in H'_v} p'_u \cdot c'_u \bigg) + \sum_{u \in V' \setminus \mathcal{H'}} p'_u \cdot c'_u \\
&\le \frac{4}{3} \cdot \sum_{v\in VC} \EX[\ensuremath{\mathrm{OPT}}'_{H'_v\cup\{v'\}}] + \sum_{u \in V' \setminus \mathcal{H'}} p'_u \cdot c'_u 
\le \frac{4}{3} \cdot \EX[\ensuremath{\mathrm{OPT}}'] = \frac{4}{3} \cdot \EX[\ensuremath{\mathrm{OPT}}] \qedhere
\end{align*}
\end{proof}

\subsection{An almost best possible algorithm for orienting a hyperedge }

\begin{restatable}[]{theorem}{theoremVCSingleSet}
\label{thm:VC-single-set}
\emph{\textsc{BestVC}\xspace} has a competitive ratio at most $\min\{\frac{4}{3},\frac{n+1}{n}\}$ for the hypergraph orientation problem on a single hyperedge with $n\geq 2$ vertices and uniform query costs.
For a hyperedge with only two vertices, the algorithm is $1.207$-competitive.
\end{restatable}

The proof is in Appendix~\ref{subsec:proof-vc-single-set}. 
Our analysis improves upon a ${(n+1)}/{n}$-competitive algorithm by Chaplick et al.~\cite{chaplick20stochasticLATIN} in  case that the hyperedge has two or three vertices. Moreover, we show that this is near-optimal:
It is not hard to show a matching lower bound for two vertices and, due to Theorem~\ref{thm:generalLB43} and the theorem below, this is the best possible for three vertices, and in general the difference between the upper and lower bounds is less than 4\%.

\begin{restatable}[]{theorem}{theoremLBSingleSetUniform}
\label{thm:lb1setuniform}
Any algorithm for orienting a single hyperedge with $n+1 \geq 2$ vertices has competitive ratio at least ${n^2}/({n^2-n+1})$, even for uniform query costs.
\end{restatable}

Note that Theorem~\ref{thm:VC-single-set} is in contrast to the problem of orienting a hyperedge with arbitrary query costs:
In this setting,~\cite{chaplick20stochasticLATIN} showed that the algorithm is $1.5$-competitive, which matches the corresponding lower bound for vertex cover-based algorithms of Theorem~\ref{theorem:VC_based_LB}.

