Query Minimization under Stochastic Uncertainty

We study problems with stochastic uncertainty information on intervals for which the precise value can be queried by paying a cost. The goal is to devise an adaptive decision tree to find a correct solution to the problem in consideration while minimizing the expected total query cost. We show that, for the sorting problem, such a decision tree can be found in polynomial time. For the problem of finding the data item with minimum value, we have some evidence for hardness. This contradicts intuition, since the minimum problem is easier both in the online setting with adversarial inputs and in the offline verification setting. However, the stochastic assumption can be leveraged to beat both deterministic and randomized approximation lower bounds for the online setting.

The literature describes two kinds of algorithms for this setting. Though the nomenclature varies, we adopt the following one. An adaptive algorithm may decide which queries to perform based on results from previous queries. An oblivious algorithm, however, must choose the whole set of queries to perform in advance; i.e., it must choose a set of queries that certainly allow the problem to be solved without any knowledge of the actual values. 1 Two main approaches have been proposed to analyze both types of algorithms. In the first, an oblivious (adaptive) algorithm is compared to a hypothetical optimal oblivious (adaptive) strategy; this is the approach in [21,33,39,40]. However, for more complex problems, and in particular for adaptive algorithms, it usually becomes more difficult to understand the optimal strategy. A second (more robust) approach is competitive analysis, which is a standardized metric for online optimization [10]. In this setting, both oblivious and adaptive algorithms are compared to an optimum query set, which we define next. For a given realization of the actual values, a set of queries is a feasible query set if, after querying all intervals in that set, one can find a solution of the underlying problem; an optimal query set is a feasible query set of minimum cost. An algorithm (either adaptive or oblivious) is α-query-competitive if its total query cost is at most α times the cost of an optimum query set. This type of analysis is performed in [6,12,19,20,30,31,33,38,45]. For NP-hard problems, since we do not expect to find the "correct" solution in polynomial time, there are two approaches in the literature: either we have an objective function which combines query and solution costs (this is how the scheduling problem is addressed in [16]), or we have a fixed query budget and the objective function is based only on the solution cost (as for the knapsack problem in [25]). Another related problem is that of, given a realization of the precise values, how to compute an optimum query set. This is often called the verification [6,14,17] or offline [31] version of the problem. This may be interesting both for performing experimental evaluation of the algorithms, as for obtaining insight for solving the corresponding oblivious/adaptive problems (as we discuss in Section 3).
Competitive analysis is, however, rather pessimistic. In particular, many problems such as minimum, sorting and spanning tree have a deterministic lower bound of 2 and a randomized lower bound of 1.5 for adaptive algorithms, and a simple 2-competitive deterministic adaptive algorithm, even if queries are allowed to return intervals [20,30,31,38]. For the sorting problem, e.g., Halldórsson and de Lima [31] showed that there is essentially one structure preventing a deterministic adaptive algorithm from having a competitive ratio better than 2.
One natural alternative to competitive analysis is to assume stochastic inputs, i.e., that the precise value in each interval follows a known probability distribution, and we want to build a decision tree specifying a priority ordering for querying the intervals until the correct solution is found, so that the expected total query cost is minimized. 2 In this paper, we study the sorting problem and the problem of identifying the data item with minimum value in this setting. Some literature is devoted to a similar goal of this paper, but we argue that there are some essential differences. One first line of work consists of the stochastic probing problem [1,24,26,27,28,29,44], which is a general stochastic optimization problem with queries. Even though those works presented results for wide classes of constraints (such as matroid and submodular), they differ in two ways from our work. First, they assume that only elements that are queried can be in a solution of the underlying problem, or that the objective function is based on the expectation of the non-queried elements. Second, the objective function is either a combination of the solution and query costs, or there is a fixed budget for performing queries. Since most of these variants are NP-hard [24], some papers [27,44] focused on devising approximation algorithms, while others [24,28] on bounding the ratio between an oblivious algorithm and an optimal adaptive algorithm (the adaptive gap). Another very close work is that of Welz [45,Section 5.3] and Maehara and Yamaguchi [37], who, like us, assume that a solution may contain non-queried items. Welz presented results for the minimum spanning tree and traveling salesman problems, but under strong assumptions on the probability distributions. Maehara and Yamaguchi devised algorithms for a wide class of problems, that also yield improved approximation algorithms for some classical stochastic optimization problems. However, both works focus on obtaining approximate solutions for the underlying problem, while we wish to obtain an exact one, and they only give asymptotic bounds on the number of queries performed, but do not compare this to the expected cost of an optimum query set. To sum up, our work gives a better understanding on how the stochastic assumption differs from the competitive analysis, since other assumptions are preserved and we use the same metric to analyze the algorithms: minimizing query cost while finding the correct solution.
Our results. We prove that, for the sorting problem with stochastic uncertainty, we can construct an adaptive decision tree with minimum expected query cost in polynomial time. We devise a dynamic programming algorithm which runs in time O(n 3 d 2 ) = O(n 5 ), where n is the number of uncertainty intervals and d is the clique number of the interval graph induced by the uncertainty intervals. We then discuss why simpler strategies fail, such as greedy algorithms using only local information, or relying on witness sets, which is a standard technique for solving query-minimization problems with adversarial inputs [12,20]. We also discuss why we believe that the dynamic programming algorithm cannot be improved to o(n 3 ).
Surprisingly, on the other hand, we present evidence that finding an adaptive decision tree with minimum expected query cost for the problem of finding the data item with minimum value is hard, although the adaptive online version (with adversarial inputs) and the offline (verification) version of the problem are rather simple. We prove that the (locally) optimal decision tree conditioned to first querying the leftmost interval can be computed easily, and that, in a (globally) optimal decision tree, the leftmost interval is queried first or last. This also implies that, for any subtree of an optimal decision tree, one branch can be calculated easily. The hard part of the problem occurs when the global optimum does not query the leftmost interval first, and the question becomes how to find the order in which the other intervals are considered in the "hard branch" of the decision tree. We discuss why various heuristics fail in this case. A simple approximation result with factor 1 + 1/d 1 for uniform query costs, where d 1 is the degree of the leftmost interval in the interval graph, follows from the adaptive online version with adversarial inputs [33]. For arbitrary query costs, we show that the stochastic assumption can be used to beat both deterministic and randomized lower bounds for the adaptive online version with adversarial inputs.
Other related work. One interesting related problem was studied by van der Hoog et al. [32]: how to preprocess a set of intervals so that the actual numbers can be sorted efficiently after their precise values are revealed. Ajtai et al. [2] studied an uncertainty variant of the sorting problem in which a comparison between two values may be imprecise, and the goal is to minimize the number of comparisons to sort the values within a given precision. Braverman and Mossel [11] studied the problem of estimating the most probable ordering of a set of values in two models of uncertainty: (1) when comparisons are not reliable, and (2) when a permutation of the original ordering is sampled within a given probability distribution.
Our work falls into the wide area of stochastic optimization [9], and in particular multi-stage stochastic optimization [41]. Problems with uncertainty data described by intervals have also been studied under the framework of robust optimization [4,34,46]. A classical paper on multi-stage robust optimization is [15]. For surveys on robust optimization, see [7,8].
Organization of the paper. Section 2 is devoted to the sorting problem with stochastic uncertainty, and Section 3 to the problem of finding the minimum data item. We conclude the paper with future research questions in Section 4.

Sorting
The problem is to sort n numbers v 1 , . . . , v n ∈ R whose actual values are unknown. We are given n open intervals I 1 , . . . , I n such that v i ∈ I i = (ℓ i , r i ). We can query interval I i by paying a cost w i , and after that we know the value of v i . We want to find a permutation π : [n] → [n] such that v i ≤ v j if π(i) < π(j) by performing a minimum-cost set of queries. We focus on adaptive algorithms, i.e., we can make decisions based on previous queries. We are interested in a stochastic variant of this problem in which v i follows some known probability distribution on I i . The only constraints are that (1) values in different intervals have independent probabilities, (2) for any subinterval (a, b) ⊆ I i , we can calculate Pr[v i ∈ (a, b)] in constant time 3 , and (3) the known information on the probability distribution cannot be used to shorten the endpoints of any uncertainty interval 4 . The goal is to devise a strategy (i.e., a decision tree) to query the intervals so that the expected query cost is minimized. More precisely, this decision tree must tell us which interval to query first and, depending on where its value falls, which interval to query second, and so on, until we have enough information to find the permutation π. Definition 1. Two intervals I i and I j such that r i > ℓ j and r j > ℓ i are dependent. Two intervals that are not dependent are independent.
The following lemma and proposition are proved in [31]. The lemma tells us that we have to remove all dependencies in order to be able to sort the numbers.

Lemma 2 ([31]). The relative order between two intervals can be decided without querying either of them if and only if they are independent.
Proposition 3 ( [31]). Let I i and I j be intervals with actual values v i and v j . If v i ∈ I j (and, in particular, when I i ⊆ I j ), then I j is queried by every feasible query set.
Note that the dependency relation defines an interval graph, where we have a vertex for each interval, and two vertices are adjacent if the corresponding intervals intersect [36]. Prop. 3 implies that we can immediately query any interval containing another interval, hence we may assume a proper interval graph (that is, without nested interval pairs) [42]. We may also assume the graph is connected, since the problem is independent for each component, and that there are no single-point intervals, as they would give a non-proper or disconnected graph.

An optimal algorithm
We describe a dynamic programming algorithm to solve the sorting problem with stochastic uncertainty. Since we have a proper interval graph, we assume intervals are in the natural total order, with ℓ 1 < · · · < ℓ n and r 1 < · · · < r n . We also pre-compute the regions S 1 , . . . , S t defined by the intervals, where t ≤ 2n − 1. A region is the interval between two consecutive points in the set n i=1 {ℓ i , r i }; we assume that the regions are ordered. We write S x = (a x , b x ) with a x < b x , and we denote by I x (y, z) = {i : S x ⊆ I i ⊆ (a y , b z )} the indices of the intervals totally contained in (a y , b z ) that contain S x . For simplicity we assume that, for any interval I i and any region S x , 0; this is natural for continuous probability distributions, and for discrete distributions we may slightly perturb the distribution support so that this is cascading area (a) cascading area enforced (we give more detail in Section 2.4). Since the dependency graph is a connected proper interval graph, we can also assume that each interval contains at least two regions. Before explaining the recurrence, we first examine how Prop. 3 reduces the space of feasible query sets with an example. In Figure 1(a), suppose we first decide to query I 3 and its value falls in region S 5 . Due to Prop. 3, all intervals that contain S 5 , namely I 2 and I 4 , have to be queried as well. In Figure 1(b), we assume that v 2 falls in S 3 and v 4 falls in S 6 . This forces us to query I 1 but also implies that I 5 can be left unqueried. Therefore, each time we approach a subproblem by first querying an interval I i whose value falls in region S x , we are forced to query all other intervals that contain S x , and so on in a cascading fashion, until we end up with subproblems that are independent of current queried values. To find the best strategy, we must pick a first interval to query, and then recursively calculate the cost of the best strategy, depending on the region in which its value falls. Here, the proper interval graph can be leveraged by having the cascading procedure follow the natural order of the intervals.
We solve the problem by computing three tables. The first table, M , is indexed by two regions y, z ∈ {1, . . . , t}, and M [y, z] is the minimum expected query cost for the subinstance defined by the intervals totally contained in (a y , b z ). Thus, the expected query cost of an optimum decision tree for the whole problem is M [1, t]. To compute M [y, z], we suppose the first interval in (a y , b z ) that is queried by the optimum decision tree is I i . Then, for each region S x ⊆ I i , when v i ∈ S x , we are forced to query every interval I j with j ∈ I x (y, z) and this cascades, forcing other intervals to be queried depending on where v j falls. So we assume that, for all j ∈ I x (y, z), v j falls in the area defined by regions z ′ , z ′ + 1, . . . , y ′ − 1, y ′ , with z ′ ≤ x ≤ y ′ , and that this area is minimal (i.e., some point is in S z ′ , and some point is in S y ′ ). We call this interval (a z ′ , b y ′ ) the cascading area of I i in I x (y, z). In Figure 1(b), we have i = 3, x = 5, z ′ = 3 and y ′ = 6. As the dependency graph is a proper interval graph, the remaining intervals (which do not contain S x ) are split in two independent parts, and we compute the resulting expected query cost using two tables, L and R, which we describe next. So the recurrence for M [y, z] is where p(y, z, i, x, z ′ , y ′ ) is the probability that (a z ′ , b y ′ ) is the cascading area of I i in I x (y, z). We omit how to calculate this probability. The definitions of L and R are symmetric, so we focus on L. For region indices y, z, let I j ′ be the leftmost interval totally contained in (a y , b z ). Now, L[y, z ′ , j] is the minimum expected query cost of solving the subproblem consisting of intervals I j ′ , I j ′ +1 , . . . , I j−1 , assuming that a previously queried point lies in the region S z ′ . We ensure that z ′ is the leftmost region in (a y , b z ) that contains a queried point, so that we query all intervals that contain some point. For example, in Figure 1(b), after querying I 2 , I 3 and I 4 , the left subproblem has z ′ = 3 and j = 2. It holds that L can be calculated in the following way. If no interval before I j contains S z ′ , then the cascading is finished and we can refer to table M for regions y, y + 1, . . . , z ′ − 1. Otherwise I j−1 must contain S z ′ , we query it, and either v j−1 falls to the right of a z ′ and we proceed to the next interval, or v j−1 falls in a region S k with k < z ′ , and we proceed to the next interval with the leftmost queried point now being in S k . Thus, we have We illustrate this in Figure 2. In Figure 2(a), the subproblem contains I j−1 , I j−2 , . . ., and the leftmost queried point is in S z ′ . Since S z ′ ⊆ I j−1 , we query I j−1 and assume v j−1 falls in a region S k . In Figure 2(b), we have that k ≥ z ′ , so we recurse on L[y, z ′ , j − 1]; this will recurse on M [y, z ′ − 1] in its turn, since S z ′ ⊆ I j−2 . In Figure 2(c), we have that k < z ′ , so we recurse on L[y, k, j − 1], which in its turn will have to query I j−2 .
Analogously for table R, let I j ′ be the rightmost interval totally contained in (a z , b y ). We want to find the best strategy for intervals I j+1 , . . . , I j ′ , assuming that the rightmost queried point is contained in S y ′ . Thus, we have Observe that the definition of table L only depends on which is the leftmost region in the cascading area (and, symmetrically, R only depends on the rightmost region). Therefore, we can simplify the recurrence for table M to if (a y , b z ) contains less than 2 intervals min Ii⊆(ay,bz) Sx⊆Ii where p L (y, z, i, x, z ′ ) is the probability that S z ′ is the leftmost region in the cascading area of I i in I x (y, z), and p R (y, z, i, x, y ′ ) is the probability that S y ′ is the rightmost region. We explain how to calculate these probabilities in Section 2.3. At this point it is not hard to see that the next theorem follows by a standard optimal substructure argument. We present a proof for the sake of completion. Proof. We prove that, for any 1 ≤ y ≤ z ≤ t, the value M [y, z] is the expected query cost of a best decision tree for the subproblem defined by the intervals totally contained in (a y , b z ). The proof is by induction on the number of intervals totally contained in (a y , b z ). If it contains less than two intervals, then no query has to be done to solve this subproblem and the claim follows, so let us assume it contains at least two intervals.
Let us define more precisely how the decision tree for a subproblem is structured. Let I be a collection of intervals and queried points, with at least two dependent elements, and let T (I) be a best decision tree for solving the subproblem defined by I. The root of the tree indicates which interval I i to query first. Then, for each region S x contained in I i , the tree has a branch which is the decision tree for the remaining intervals, conditioned to the fact that v i ∈ S x ; we can write this subtree as T (( is the same, since v x will be dependent to the same intervals, and the dependencies between other intervals do not change. The expected cost of the decision tree encoded by T (I) is then The leaves of the tree will correspond to collections of independent intervals, and will have query cost zero.
If a subtree T (I) contains a queried value v x and a non-queried interval I j with v x ∈ I j , then Prop. 3 says that any feasible query set for I must query I j . This implies that I j is queried in the path between the root and any leaf of the tree. Thus, it is easy to see that there is a decision tree for this subproblem with the same cost in which the first query is I j . If more than one interval contains a queried value v x , then we can query them before other intervals, and in any order, so we can actually query all of them at the same time, and have a root with branches for each combination of regions in which the values fall.
The algorithm starts by querying an interval I i and, depending on the region S x in which v i falls, queries all intervals that contain S x . Since we have a proper interval graph, the remaining intervals are divided into two independent suproblems. Also, if the minimal area containing the regions in which the values fall is the same, then the cost of the subtree is the same, since the same intervals will contain a point queried at this time; this implies that each cascading area is a single disjoint event. Given a cascading area (a z ′ , b y ′ ), the remaining problem consists of finding the best decision tree for two subproblems: one considering that the intervals to the left of S x have not been queried and that the leftmost queried point is in S z ′ , and another that the intervals to the right of S x have not been queried and that the rightmost queried point is in S y ′ . This is precisely the definition of tables L and R; thus, if the recurrences for tables L and R are correct, then the theorem follows by an optimal substructure argument.
So let us prove that the recurrence for table L[y, z ′ , j] is correct; the proof for table R is analogous. Let us recall the definition: L[y, z ′ , j] is the minimum expected cost of solving the subinstance of (a y , b z ) (for some z ≥ z ′ ) consisting of intervals I j ′ , I j ′ +1 , . . . , I j−1 , where I j ′ is the leftmost interval totally contained in (a y , b z ), assuming that the leftmost queried point is contained in then all intervals in I j , I j+1 , . . . have a value to the right of a z ′ , and thus any feasible query set to the intervals totally contained in (a y , b z ′ −1 ) is feasible to complement the current decision tree. Thus, by an optimal substructure argument, Prop. 3 implies that I j−1 must be queried in any feasible query set of the subproblem, and thus can be the first interval queried in this subproblem. When querying I j−1 , we ensure that the leftmost region with a queried point is updated correctly, so the last term in the recurrence for L[y, z ′ , j] is correct by an optimal substructure argument.
The recurrences can be implemented in a bottom-up fashion in time O(n 5 ): if we precompute the value of p L (y, z, i, x, z ′ ) and p R (y, z, i, x, y ′ ), then each entry of M is computed in time O(n 3 ), and each entry of L and R can be computed in linear time. It is possible to precompute p L and p R in time O(n 3 ), which we discuss in Section 2.3. A more careful analysis shows that the time consumption of the whole algorithm is O(n 3 d 2 ), where d is the clique number of the interval graph. First, we show that each entry of M can be computed in time O(nd 2 ). Note that, in a proper interval graph, an interval contains at most 2d − 1 regions, so we have at most 2d − 1 choices of S x for each I i . It holds that I x (y, z) contains at most d intervals, since every such interval contains S x . Moreover, for a given choice of S x , note that z ′ cannot go further left than the leftmost region of the leftmost interval that contains S x , and since z ′ ≤ x we have at most 2d − 1 choices of z ′ ; an analogous argument applies to y ′ . Now we argue that we only need to compute L[y, z ′ , j] if S z ′ ⊆ I j : the leftmost queried point cannot be to the right of I j , since we assume I j was already queried, and cannot be to the left of I j , since we assume I j is the leftmost queried interval. Moreover, it is clear that each entry of L can be computed in time O(d). Analogous arguments apply to table R. Finally, in Section 2.3 we also refine the analysis to argue that the probabilities can be precomputed in time O(n 2 d).
We now argue that an actual optimal decision tree can be constructed using polynomial time and space, if we represent it by a directed acyclic graph (DAG). First, we augment table M with an entry for the interval that is queried first in each subproblem, so we can track what is the best option. Then, we create one node in the DAG for each entry in tables M, L, R. Each node will then have a polynomial number of children: for table M , we have a child for each choice of x, z ′ , y ′ and, for tables L and R, we have a child for each choice of k. Note that the same entry of the table is used by overlapping subproblems, so we can do the same for the nodes in the DAG. It is not hard to see that this construction can be done using at most as much time as for computing the original tables.
It seems difficult to improve this dynamic programming algorithm to something better than O(n 3 · poly(d)). Note that the main information that the decision tree encodes is which interval should be queried first in a given independent subproblem (and there are Ω(n 2 ) such subproblems). We could hope to find an optimal substructure that would not need to test every interval as a first query, and that this information could somehow be inferred from smaller subproblems. However, consider I 1 = (0, 100), I 2 = (6, 105), and I 3 = (95, 198), with uniform query costs and uniform probability distributions. The optimum solution for the first two intervals is to first query I 1 , but the optimum solution for the whole instance is to start with I 2 . Thus, even though I 2 is a suboptimal first query for the smaller subproblem, it is the optimal first query for the whole instance. This example could be adapted to a larger instance with more than d intervals, so that we need at least a linear pass in n to identify the best first query.

Simpler strategies that fail
It may seem that our dynamic programming strategy above is overly complex, and that a simpler algorithm may suffice to solve the problem. Below, we show sub-optimality of two such strategies.
We begin by showing that any greedy strategy that only takes into consideration local information (such as degree in the dependency graph or overlap area) fails. Consider a 5-path with intervals I 1 , . . . , I 5 , where interval I i has non-empty intersection with intervals I i−1 (if i > 1) and I i+1 (if i < 5). Let each interval have query cost 1 and an overlap of 1/3 with each of its neighbors, and the exact value be uniformly distributed in each interval. It can be shown by direct calculation that if we query I 2 (or, equivalently, I 4 ) first, then we have an expected query cost of at most 29/9 = 3.22, while querying I 3 first yields an expected query cost of at least 11/3 = 3.66. However, a greedy strategy that only takes into consideration local information cannot distinguish between I 2 and I 3 .
One technique that has been frequently applied in the literature of uncertainty problems with query minimization is the use of witness sets. A set of intervals W is a witness if a correct solution for the underlying problem cannot be computed unless at least one interval in W is queried, even if all other intervals not in W are queried. Witness sets are broadly adopted because they simplify the design of querycompetitive adaptive algorithms. If, at every step, an algorithm queries disjoint witness sets of size at most α, then this algorithm is α-query-competitive. This concept was proposed in [12]. For the sorting problem, by Lemma 2, any pair of dependent intervals constitute a witness set. However, we cannot take advantage of witness sets for the stochastic version of the problem, even for uniform query costs and uniform probability distributions, and even if we take advantage of the proper interval order. Consider the following intervals: (0, 100), (95, 105), (98,198). The witness set consisting of the first two intervals may lead us to think that either of them is a good choice as the first query. However, the unique optimum solution first queries the third interval. (The costs are 843/400 = 2.1075 if we first query the first interval, 277/125 = 2.216 if we first query the second interval, and 4182/2000 = 2.0915 if we first query the third interval.)

Computing the probability of a cascading area
Let us discuss how to calculate p L (y, z, i, x, z ′ ), which is the probability that, given that v i ∈ S x , it holds that v k > a z ′ for each k ∈ I x (y, z), and some j ∈ I x (y, z) has v j ∈ S z ′ . (The arguments are symmetric for p R (y, z, i, x, y ′ ), so we omit them.) Note that, considering the definition of table M , we can assume that Pr[v i ∈ S x ] > 0; otherwise we don't need to compute p L (y, z, i, x, z ′ ). We will also assume that z ′ = x, and the remaining case can be computed similarly.
Let us fix the values y, z, x, and denote I = I x (y, z), denote the similar probability defined for the set of intervals Note that all divisions in the equation are defined, because we assumed that Pr[v i ∈ S x ] > 0 and z ′ < x.
Since q L (z ′ ) does not depend on i, for each fixed x, y, z, it can be computed in linear time, so all q L (z ′ ) can be computed for all x, y, z in time O(n 5 ). Given this precomputation, all values p L (z ′ , i) for all y, z, i, x, z ′ can be precomputed in O(n 5 ) time.
We can further improve the runtime to O(n 4 ) as follows. Here, we fix z ′ and y, z, and compute q L (z ′ ) for various values of x, so let us now denote q L (x) = q L (z ′ ). Recall that q L (x) = j∈Ix(y,z) Pr[v j > a z ′ ], and note that each factor in this product is non-zero due to assumption (3) at the beginning of Section 2. We compute q L (x) sequentially from x = z ′ to x = x * , where x * is the rightmost region such that there is an interval that contains both S z ′ and S x * . Given q L (x) for some x, q L (x+1) is computed by removing from the product intervals in I x (y, z) \ I x+1 (y, z) and including intervals in I x+1 (y, z) \ I x (y, z). The remainder of the product is reused. Observe that, during this computation, each interval that contains a region in (a z ′ , b x * ) is included in (and removed from) the product exactly once. Therefore, the computation corresponding to fixed values of y, z, z ′ can be done in time proportional to the number of regions x between z ′ and x * plus the number of intervals that contain some region in (a z ′ , b x * ), that is, in O(n) time. Thus, the computation of the whole table takes O(n 4 ) time.
Finally, the preprocessing time can be further reduced (still having constant time computation of p L (· · · ) after preprocessing), by decomposing the table for q into two parts, based on the following observation. The first table is indexed by y, x, z ′ , while the second one by z, x, z ′ . Consider the value q L (y, z, x, z ′ ). This is a product of probabilities ranging over intervals I x (y, z). The observation is that where J x (z, t) is the set of intervals that contain both S x and S z and do not end at b z . Thus, x, z ′ ) if the denominator is non-zero, and otherwise q L (y, z, x, z ′ ) = q L (y, t, x, z ′ ), where q ′ L is defined similarly as q L , except it ranges over J x (z, t). The subtables q L and q ′ L can be computed in O(n 3 ) time using the observations in the previous paragraph.
To refine the analysis, recall that each interval in a proper interval graph contains at most 2d − 1 regions. Since we only consider pairs z ′ , x such that there is an interval that contains both S z ′ and S x , we have at most 2d − 1 choices of x for each choice of z ′ . Thus, we only need time O(d) to compute q L (y, z, z ′ ) for all values of x and fixed y, z, z ′ , and the whole preprocessing can be done in time O(n 2 d).

Allowing arbitrary probabilities on interval endpoints
In this section we discuss how to remove the assumption that 1. If there is some interval I j with ℓ j = b x but no interval j ′ with r j ′ = b x , then we can simply move the probability Pr Note that we did not need to query I j if originally v i = b x ; we could simply make π(i) < π(j). On the other hand, all intervals that originally contained b x will contain b x − ε, so they will be queried if originally v i = b x .

We can do a symmetric operation if there is some interval
3. If there is an interval I j with ℓ j = b x and an interval I j ′ with r j ′ = b x , then we can "shift" the whole ray (b x , +∞) to the right by 2ε, for some ε > 0. More formally, any interval I k with ℓ k ≥ b x will have a new left endpoint ℓ ′ k = ℓ k + 2ε; any interval I k with r k > b x will have a new right endpoint r ′ k = r k + 2ε; for any α > b x , we will move the probability we did not need to query I j or I j ′ if originally v i = b x (we could simply make π(j ′ ) < π(i) < π(j)), and all intervals that originally contained b x will also contain b x + ε (so they will be queried if originally Note that the last transformation creates new regions, but the total number of regions will be at most twice the original, so the time consumption does not increase asymptotically. Moreover, the algorithm can be modified to allow closed and half-open intervals, and thus discrete distributions with finite support. We only need to be careful when v i = b x for some queried interval I i and some region S x : we do not need to query all intervals that contain S x , but only intervals I j with b x ∈ (ℓ j , r j ).

Finding the Minimum
We also consider the problem of finding the minimum (or, equivalently, the maximum) of n unknown values v 1 , . . . , v n . Note that we do not need to know the precise minimum value, but just the data item that contains it; therefore, in some cases it is not necessary to query the corresponding interval. We assume that all intervals are open 5 , and that they are sorted by the left endpoint, i.e., ℓ 1 ≤ ℓ 2 ≤ · · · ≤ ℓ n . Regarding the probability distributions, we also assume constraints (1)-(3) described at the beginning of Section 2. Let I = {I 1 , . . . , I n }.
We begin by discussing some assumptions we can make. First, we can assume that the interval graph is a clique: with two independent intervals, we can remove the one on the right. (However, we cannot assume a proper interval graph, as we did for sorting: the argument that one of the nested intervals has to be queried no longer holds, since here we are only interested in finding the minimum rather than the total order.) The last assumption is that I 1 does not contain another interval; it is based on the following proposition and implies that r 1 = min i r i . Note that it also implies that ℓ 1 < ℓ 2 , . . . , ℓ n . Proposition 5. If I 1 contains some I j , then I 1 is queried in every feasible query set.
Proof. Suppose by contradiction that there is a feasible query set Q that does not contain I 1 . Since ℓ 1 = min i ℓ i , we must have Q = I \ {I 1 } and v i > r 1 for every I i ∈ Q, otherwise we cannot decide if v 1 is the minimum. However, assuming both v j > r 1 and I j ⊆ I 1 is a contradiction.
It is also useful to understand how to find an optimum query set, i.e., to solve the verification problem assuming we know v 1 , . . . , v n . Lemma 6. The optimum query set either (a) queries interval I i with minimum v i and each interval I j with ℓ j < v i ; or (b) queries all intervals except for I 1 , if v 1 is the minimum, v j > r 1 for all j > 1, and this is better than option (a).
Option (b) can be better not only due to a particular non-uniform query cost configuration, but also with uniform query costs, when v 1 ∈ I 2 , . . . , I n . Note also that I 1 is always queried in option (a).
Proof. First let us consider the case when v 1 is the minimum. If v j < r 1 for some j > 1, then I 1 has to be queried even if all other intervals have already been queried, due to Prop. 5. Thus, the only situation in which I 1 may not be queried is when v j > r 1 for all j > 1, and in this case clearly we have to query all other intervals, since otherwise we cannot decide who is the minimum. Now we prove that, if v i is the minimum with i = 1, then I i must be queried. Since v i is the minimum, all other values fall to the right of ℓ i . In particular, v 1 ∈ I i , since I 1 has minimum r 1 . Thus, even if all other intervals have already been queried, I i must be queried due to Prop. 5.
It remains to prove that, for any i ≥ 1, if v i is minimum and I i is queried, then all intervals with ℓ j < v i must also be queried; we actually prove that I 1 , . . . , I j must be queried, by induction on j. The base case is j = 1, and if i = 1 the claim follows from Prop. 5, since v i < r 1 and ℓ 1 < ℓ i . So assume j > 1; note that ℓ j−1 ≤ ℓ j < v i thus, by induction hypothesis, I 1 , . . . , I j−1 must be queried. Since v i is the minimum, v k ≥ v i > ℓ j , for k = 1, . . . , j − 1. Therefore, after I 1 , . . . , I j−1 are queried, I j is the leftmost interval, and must be queried due to Prop. 5, since it contains v i .
We first discuss what happens if the first interval we query is I 1 . In Figure 3(a), we suppose that v 1 ∈ S 3 . This makes I 2 become the leftmost interval, so it must be queried, since it contains v 1 . At this point we also know that we do not need to query I 4 , since v 1 < ℓ 4 . After querying I 2 , we have two possibilities. In Figure 3(b), we suppose that v 2 ∈ S 2 , so we already know that v 2 is the minimum and no other queries are necessary. In Figure 3(c), we suppose that v 2 ∈ S 6 , so we still need to query I 3 to decide if v 1 or v 3 is the minimum. Note that, once I 1 has been queried, we do not have to guess which interval to query next, since any interval that becomes the leftmost interval will either contain v 1 or will be to the right of v 1 . Since this is an easy case of the problem, we formalize how to solve it. The following claim is clear: if we have already queried I 1 , . . . , I i−1 and v 1 , . . . , v i−1 > ℓ i , then we have to query I i . (This relies on I i having minimum ℓ i among I i , . . . , I n .) If we decide to first query I 1 , then we are discarding option (b) in the offline solution, so all intervals containing the minimum value must be queried. The expected query cost is then n i=1 w i · Pr[I i must be queried]. Given an interval I i , it will not need to be queried if there is some I j with v j < ℓ i , thus the former probability is the probability that no value lies to the left of I i . Since the probability distribution is independent for each interval, the expected query cost will be This can be computed in O(n 2 ) time. Now let us consider what happens if an optimum decision tree does not start by querying I 1 , but by querying some I k with k > 1. When we query I k , we have two cases: (1) if v k falls in I 1 , then we have to query I 1 and proceed as discussed above, querying I 2 if v 1 > ℓ 2 , then querying I 3 if v 1 , v 2 > ℓ 3 and so on; (2) if v k / ∈ I 1 , then v k falls to the right of ℓ i , for all i = k, so essentially the problem consists of finding the optimum decision tree for the remaining intervals, and this value will be independent of v k . Therefore, the cost of querying I k first is Thus, we can see that a decision tree can be specified simply by a permutation of the intervals, since the last term in the last equation is fixed. More precisely, let a(1), . . . , a(n) be a permutation of the intervals, where a(k) = i means that I i is the k-th interval in the permutation. We have two types of subtrees. Given a subset X k = {a(k), . . . , a(n)} that contains 1, letT k be the tree obtained by first querying I 1 , then querying the next leftmost interval in X k if it contains v 1 and so on. The second type of subtree T k is defined by a suffix a(k), . . . , a(n) of the permutation. If a(k) = 1, then T k is a decision tree with a root querying I a(k) and two branches. One branch, with probability Pr[v a(k) ∈ I 1 ], consists ofT k+1 ; the other branch, with probability Pr[v a(k) / ∈ I 1 ], consists of T k+1 . If a(k) = 1, then T k =T k , unless k = n, in which case T n will be empty: I 1 does not need to be queried, because all other intervals have already been queried and their values fall to the right of I 1 . We have that cost(T k ) if a(k) = 1 and k = n cost(T k ), if a(k) = 1 and k < n w a(k) + Pr[v a(k) ∈ I 1 ] · cost(T k+1 |v a(k) ∈ I 1 ) + Pr[v a(k) / ∈ I 1 ] · cost(T k+1 ), otherwise.
Note that in the last case we need to condition cost(T k+1 ) to the fact that v a(k) ∈ I 1 . We have that It holds that, if I 1 is not the last interval in a decision tree permutation, then it is always better to move I 1 one step towards the beginning of the permutation. This fact is formalized in the following lemma.
Lemma 7. Given a decision tree permutation I k I 1 I k ′ · · · of a subset S, with |S| ≥ 3 and I 1 ∈ S, it costs at least as much as the cost of I 1 I k I k ′ · · · .
Proof. Let 1[A] be the indicator variable of the event A, i.e., 1[A] = 1 if A is true, and zero otherwise. The cost of where the first equality holds since the probability distributions are independent, so Pr[v j > ℓ i |v k ∈ I 1 ] = Pr[v j > ℓ i ] unless j = k. The second equality holds since ℓ i < r 1 for all i, so Pr[v k > ℓ 1 |v k / ∈ I 1 ] = 1. The third equality holds since Pr[v k / ∈ I 1 ] + Pr[v k ∈ I i ] = 1 and by Bayes' theorem. On the other hand, if we swap I k and I 1 , then the cost is since j<k Pr[v j > ℓ k ] ≤ 1, and the last value is precisely the cost of the former permutation. This lemma implies, by induction, that the optimum decision tree either first queries I 1 , or has I 1 at the end of the permutation. If I 1 is the last interval in the permutation, then it does not have to be queried if all other values fall to its right. Thus it may be that, in expectation, having I 1 as the last interval is optimal.
We do not know, however, how to efficiently find the best permutation ending in I 1 . Simply considering which interval begins or ends first, or ordering by Pr[v i ∈ I 1 ] is not enough. To see this, consider the following two instances with uniform costs and uniform probabilities. In the first, I 1 = (0, 100), I 2 = (5, 305) and I 3 = (6, 220); the best permutation is I 2 , I 3 , I 1 and has cost 2.594689. If we just extend I 2 a bit to the right, making I 2 = (5, 405), then the best permutation is I 3 , I 2 , I 1 , whose cost is 2.550467.
If there was a way to determine the relative order in the best permutation between two intervals I j , I k = I 1 , simply by comparing some value not depending on the order of the remaining intervals (for example, by comparing the cost of I j I k I 1 · · · and I k I j I 1 · · · ), then we could find the best permutation easily. Unfortunately, the ordering of the permutations is not always consistent, i.e., given a permutation, consider what happens if we swap I j and I k : it is not always best to have I j before I k , or I k before I j . Consider intervals I 1 = (0, 1000), I 2 = (3, 94439), I 3 = (8, 6924), and I 4 = (9, 2493), with uniform query cost and uniform probability distributions. The best permutation is I 4 , I 3 , I 2 , I 1 , and the costs of the permutations ending in I 1 are as follows. Note that it is sometimes better that I 2 comes before I 3 , and sometimes the opposite. This issue also seems to preclude greedy and dynamic programming algorithms from succeeding. It seems that it is not possible to find an optimal substructure, since the ordering is not always consistent among subproblems and the whole problem. We have implemented various heuristics and performed experiments on random instances, and could always find instances in which the optimum was missed, even for uniform query costs and uniform probabilities.
Another reason to expect hardness is that the following similar problem is NP-hard [24]. Given stochastic uncertainty intervals I 1 , . . . , I n , costs w 1 , . . . , w n , and a query budget C, find a set S ⊆ {1, . . . , n} with w(S) ≤ C that minimizes E[min i∈S v i ].
Note that the decision version of our problem (whether there is a decision tree with expected cost ≤ α) is in NP as we can represent a decision tree using linear space (by a permutation of the intervals) and compute its cost in polynomial time.

Approximation Algorithms
Good approximation algorithms have been proposed for the adaptive online version with adversarial inputs [33]. If query costs are uniform, then first querying I 1 costs at most opt + 1, which yields a factor 1 + 1/d 1 , where d 1 is the degree of I 1 in the interval graph. For arbitrary costs, there is a randomized 1.5-approximation algorithm using weighted probabilities in the two strategies stated in Lemma 6. Those results apply to the stochastic version of the problem simply by linearity of expectation.
Theorem 8. The stochastic minimum problem with uncertainty admits a (1 + 1/d 1 )-approximation for uniform query costs, and a randomized 1.5-approximation for arbitrary costs.
Proof. For any path between the root and a leaf in the decision tree, the result holds in the worst case, so it holds in expectation.
Those results have matching lower bounds for the adaptive online setting with adversarial inputs, and for arbitrary query costs there is a deterministic lower bound of 2. We show that the stochastic assumption can be used to beat those lower bounds for arbitrary costs. First, the randomized 1.5-approximation algorithm can be derandomized, simply by choosing which strategy has smaller expected query cost: either first querying I 1 , or first querying all other intervals and if necessary querying I 1 . We know how to calculate both expected query costs in time O(n 2 ); the latter is i>1 Theorem 9. There is a deterministic 1.5-approximation algorithm for the stochastic minimum problem with uncertainty with arbitrary query costs.
Proof. Let V be the set of realizations of the values, and assume V is finite. (Otherwise finiteness can be attained by grouping realizations into equivalence classes based on the partition into regions.) For each V ∈ V, let C 1 (V ) be the random variable denoting the cost of first querying I 1 , then querying I 2 if v 1 ∈ I 2 , and so on, and let w(R) = i>1 w i . We partition V in sets V 1 and V R , where V ∈ V 1 if opt(V ) = C 1 (V ), and V ∈ V R if opt(V ) = w(R); note that Lemma 6 guarantees that this is indeed a partition.
. If opt * is the expected query cost of the best permutation for the stochastic problem, then where the inequality holds by bounding opt * via a "fractional" decision tree.
Now consider the solution for the stochastic problem obtained by the algorithm. Let ALG 1 be the cost of first querying I 1 , and let ALG R be the cost of first querying all other intervals. Then where the second inequality holds because Pr[V ∈ V 1 ] = 1 − ρ and C 1 (V ) ≥ w 1 for any V . On the other hand, The expected query cost of the algorithm is where the second and third inequalities hold by the properties of the geometric mean.
Ahead in Theorem 11 we propose a more refined algorithm, that we analyze according to the expected approximation ratio. In the proof above, instead, we bounded the ratio of the expected query cost and the expected optimum query cost (the latter corresponding to the fractional decision tree we use as lower bound). Since there is no fixed relation between E[A]/E[B] and E[A/B] for random variables A, B, we cannot compare the results of Theorems 9 and 11. To circumvent that, we prove the following proposition. The example used in the proof was proposed for a similar result in [5], regarding the ratio of the expected query cost and the expected optimum query cost.
Proof. Consider three intervals I 1 , I 2 , I 3 , with ℓ 1 < ℓ 2 < ℓ 3 < r 1 < r 2 , r 3 . Let the query costs be w 1 = w 3 = k and w 2 = 1, with k = (1 − 2ε)/ε 2 ; note that k > 0. Let the probability distributions be the following: The algorithm will either query I 1 and cascade, with expected query cost (the algorithm queries I 1 , then , or query {I 2 , I 3 }, and then I 1 if necessary, with expected query cost Since the first option is slightly better, the algorithm will choose that strategy. Thus, the expected approximation ratio is Next we describe a more refined deterministic algorithm, which attains expected approximation ratio at most 1.4507; a pseudocode is given in Algorithm 1. The idea is, in some sense, to try to decide between first querying I 1 or I \ {I 1 } (as the algorithm above), but in a more cautious way, taking into consideration the relationship between the query costs and the probability distributions. The algorithm has six parameters µ 1 , µ R , ρ 1 , ρ R , φ 1 , φ j ≥ 1, which are described in the analysis and are functions of the input.
Let R = I \ {I 1 }. For a set G ⊆ R, let w(G) = i∈G w i . We say that a set G ⊆ R hits I 1 if, for some interval I i ∈ G, it holds that v i ∈ I 1 ; note that Pr[G hits . First, we try to find a set G ⊆ R such that w(G) ≤ α · w(R) and Pr[G hits I 1 ] ≥ α · Pr[R hits I 1 ], for some α ∈ [1/4, 3/4]. If we manage to find such G, then we use the parameters µ 1 , µ R , defined later in the analysis, to decide between two strategies. If µ 1 ≤ µ R , then we query I 1 and cascade. Otherwise, we first query G, and if it hits I 1 then we query I 1 and cascade. If G does not hit I 1 , then we query the remaining of R, and query I 1 if necessary. The high-level reason why it is better to query G before querying all of R is the following: if R hits I 1 , then there is a good probability (at least 1/4) that G also hits I 1 , but the cost of G is bounded by 3/4 times the cost of R. Now we describe how to find G. If some interval I j ∈ R has cost at least 3w(R)/4 and the probability that R \ {I j } hits I 1 is at least Pr[R hits I 1 ]/4, then we clearly can take G = R \ {I j }. If every interval in R has cost less than 3w(R)/4, then there is a set G ′ ⊆ R with w(R)/2 ≤ w(G ′ ) ≤ 3w(R)/4 (it can be computed greedily). In this case, let β = w(G ′ )/w(R); if G ′ hits I 1 with probability at least β · Pr[R hits I 1 ], then we can take G = G ′ and α = β. Otherwise, the complement R \ G ′ has cost (1 − β) · w(R) and probability of hitting So we let G = R \ G ′ and α = 1 − β. Note that β ∈ [1/2, 3/4] and (1 − β) ∈ [1/4, 1/2], so α ∈ [1/4, 3/4]. If we do not manage to find the set G, then note that there is an interval I j with w j ≥ 3w(R)/4, but the probability of R \ {I j } hitting I 1 is less than Pr[R hits I 1 ]/4. We have two strategies, depending on whether w 1 ≤ 3w(R)/4: 1. If w 1 ≤ 3w(R)/4, then we make a deterministic choice between querying I 1 and cascading, or querying R and then I 1 if necessary. That choice is made with the parameters ρ 1 , ρ R , which are defined later in the analysis. In this case, we show that there is a high chance that I j is part of every feasible query set, and it comprises most of the cost of the instance, so the expected query cost is not far from the expected optimum.
Input: (I 1 , . . . , I n , w, Pr) We now analyze the expected approximation factor of this algorithm.
Theorem 11. Algorithm 1 has expected approximation factor at most 1.4507 for the stochastic minimum problem with uncertainty with arbitrary query costs.
Proof. Throughout the proof, we denote by C 1 the random variable consisting of the cost of querying I 1 and cascading. Let k be the maximum index such that w 1 +. . . w k ≤ w(R), and let p 1 = Pr[v 1 > ℓ k+1 ] = Pr[v 1 ∈ I k+1 ] (cf. Prop. 5). (Note that k < n because w 1 > 0.) Note that p 1 = Pr[C 1 > w(R)|R does not hit I 1 ]: this is because, if we assume that all the values in R are to the right of r 1 , then every interval I i ∈ R with v 1 ∈ I i must be queried. We also point out that p 1 is independent from the choices of the values of the intervals in R. To simplify notation, let p R = Pr[R hits I 1 ].
First, consider the case that the algorithm queries I 1 and cascades. If R hits I 1 , which happens with probability p R , then the optimal strategy is to query I 1 and cascade, as discussed in Section 3, so we are optimal. Otherwise, the optimum cost is min(w(R), C 1 ), while the algorithm pays C 1 . In this case, the approximation ratio is 1 if C 1 ≤ w(R) (which happens with probability 1 − p 1 ); otherwise (with probability p 1 ), the ratio is at most (w 1 + w(R))/w(R) = 1 + w 1 /w(R). Thus, the expected approximation ratio is at most Next, suppose we first query G. Recall that, with probability p R , R hits I 1 and it is optimal to query I 1 and cascade. Let γ = Pr[G hits I 1 |R hits I 1 ]. If G hits I 1 , then an upper bound on the query cost of the algorithm is w(G) + C 1 , while the optimum is C 1 . Since C 1 ≥ w 1 , the approximation ratio in this case is (C 1 +w(G))/C 1 ≤ 1+w(G)/w 1 ≤ 1+αw(R)/w 1 . Otherwise, in the worst case the algorithm pays w(R)+w 1 , while again, the optimum is at least w 1 , so the approximation ratio is at most (w 1 +w(R))/w 1 = 1+w(R)/w 1 . Thus, the expected approximation ratio conditioned to R hitting I 1 is at most where the first inequality holds because 1 ≥ γ ≥ α (hence γ(α − 1) ≤ α(α − 1)), and the last inequality holds because the maximum for α 2 + 1 − α in the interval [1/4, 3/4] is 13/16. If R does not hit I 1 , which happens with probability 1 − p R , the optimum cost is min(C 1 , w(R)), while the algorithm pays w(R). Conditioned to this event, the expected approximation ratio is at most Altogether, the expected approximation ratio when the algorithm first queries G is at most where we denote z = w(R)/w 1 . By definition, the expected approximation ratio of the algorithm is at most min(µ 1 , µ R ). Our goal now is to show that this minimum is upper-bounded by the claimed approximation factor.
First, consider the case when 0 < z ≤ 1; then, both µ 1 and µ R are increasing in p 1 , so we may let p 1 = 1. Then the functions to bound are f 1 (z, p R ) = 1 + (1 − p R )/z and f 2 (z, p R ) = 1 + (13/16) · p R · z. If p R ∈ {0, 1}, then min(f 1 , f 2 ) = 1, so assume p R ∈ (0, 1). In this case, for every fixed p R , it holds that f 1 is a decreasing function of z, while f 2 is an increasing function of z. Thus, for every p R , the z that maximizes min(f 1 , f 2 ) is given by f 1 (z, p R ) = f 2 (z, p R ), that is, z = 16 (1−pR) 13pR . Plugging that value of z back into f 2 , we obtain 1 + 13 16 (p R − p R 2 ), which is maximized at p R = 1/2, giving us the bound 1 + √ 13/8 < 1.4507. Now assume z > 1. Note that we may assume z < 16/3, as otherwise µ 1 ≤ 1 + 3/16. Under such assumption, the coefficient of 1 − p R in (2) is negative, which means that for every fixed p 1 and z, µ 1 is a decreasing function of p R , while µ R is an increasing function of p R . Thus, for each z and p 1 , min(µ 1 , µ R ) is maximized when µ 1 = µ R . Solving the last equation for p R (ignoring the restriction p R ∈ (0, 1)), we get The common value of µ 1 and µ R for such p R , plugging the expression above in (1) where the first inequality holds by letting p 1 = 1, which we can do since z < 16/3 implies that the left hand side is an increasing function of p 1 . The second inequality is obtained by minimizing the denominator by setting its derivative to 0: 13/16 − 1/z 2 = 0, z = 16/13. Concluding, we see that the expected approximation ratio in Case 1 is always bounded by 1 + √ 13/8 < 1.4507. Case 2, G = ∅, w 1 ≤ 3w(R)/4. In this case we make a deterministic choice between two options: either query I 1 and cascade, or query R and then query I 1 only when R hits I 1 . The choice is based on estimates ρ 1 , ρ R of the expected approximation ratio we get in either option.
First, consider the case when we query I 1 and cascade. With probability p R , the optimum is to query I 1 and cascade as discussed in Section 3. Assuming R does not hit I 1 , with probability 1−p 1 again the optimum is to query I 1 and cascade. In the remaining case, we have approximation ratio at most (w 1 + w(R))/w(R), as the optimum only queries R. Putting these cases together, we get approximation ratio at most Next, let us estimate the approximation ratio when we choose to first query R. We divide in several cases to organize the argument.
1. With probability 1 − p R , R does not hit I 1 . Conditioned on this event, with probability p 1 , the optimum queries R only, otherwise the optimum costs C 1 ≥ w 1 . Thus, we have approximation ratio at most 2. With probability p R , R hits I 1 , so the optimum is to query I 1 and cascade, and the algorithm will query all the intervals. Remember that R contains an element I j with w j ≥ 3w(R)/4, but Let p ′ 1 = Pr[v 1 ∈ I j ]. Again, note that p ′ 1 is independent from the choices in R. Conditioned on the event when R hits I 1 , we have the following cases.
(a) With probability p ′ 1 , we have that v 1 ∈ I j . Conditioned to this event, we have two subcases. i. Since we are conditioned to R hitting I 1 , by Equation (4) we have probability at least 3/4 that R \ {I j } does not hit I 1 but v j ∈ I 1 . Therefore, querying I j must be part of any feasible query set, since v 1 ∈ I j and every interval I j ′ ∈ R \ {I j } has v j ′ > r 1 (including those with j ′ < j). So we have approximation ratio at most ii. With probability at most 1/4, we use the bound of (w 1 + w(R))/w 1 .
Thus we have that the ratio conditioned to R hitting I 1 is at most We then claim that p ′ 1 ≥ p 1 . Suppose by contradiction that p ′ 1 < p 1 , then we have that j > k + 1. By the definition of k, it holds that a contradiction since we assume that w 1 ≤ 3w(R)/4. Thus, since 1 w1+3w(R)/4 ≤ 1 w1 , the approximation ratio conditioned to R hitting I 1 is at most Summing up, the expected approximation ratio assuming that we first query R is at most Note that p 1 < 1, due to our assumption on p R . Plugging back into (3), we get where A = z 2 − z + 1 ≥ 1, and B = 1 + z 2 /4 + 3z 2 /(12z + 16) − z > 0 (for all z ≥ 1). Note also that A > B holds for all z ≥ 1. We can rule out z > 11/5, as follows. Assuming z > 11/5, our bound on p R implies p R < 0.392. Let us set p R = 0.392 in the first parentheses in (7). Then we obtain a decreasing function of p R , since 1 − A/B < 0, which is maximized for p R = 0, giving us the following function of z: 1 + z−0.608 z 2 −z+1 . The latter is easily checked to be less than 1.44 for all z > 11/5. Thus, we assume that z ∈ [4/3, 11/5]. It can be checked that the value of B in this interval is bounded by 0.353. We replace B = 0.353 and p R = 1 in the denominator of (6), to get the function We optimize this for p R . If z ≤ 2, the optimum is p R = 1 − z/2, giving us the function 1 + z 2 /4 A−0.353 , while for z > 2, the optimal value is p R = 0, giving us the function 1 + z−1 A−0.353 . Both functions can rather easily be checked to be bounded by 1.41, for z ∈ [4/3, 11/5].
Case 3, G = ∅, w 1 > 3w(R)/4. To simplify notation, let us write First let us consider the case that R ′ hits I 1 , so the optimum strategy is to query I 1 and cascade. If I j is not queried, then the approximation ratio is at most If I j is queried in the cascading, then it must be part of every feasible query set, so the approximation ratio is at most w(R ′ ) + w 1 + w j w 1 + w j ≤ 7 6 .
Now let us assume that R ′ does not hit I 1 . Let p ′ 1 = Pr[v 1 ∈ I j ] and p j = Pr[v j ∈ I 1 ]; note that those are independent events.
First, consider the situation in which the algorithm queries I 1 before I j . With probability p ′ 1 , the algorithm also queries I j ; if v j ∈ I 1 (which happens with probability p j ), then both I 1 and I j need to be queried to decide which is the minimum, otherwise the optimum strategy is to query R only, as C 1 ≥ w 1 +w j but w(R) = w j + w(R ′ ) ≤ w j + w 1 /3. With probability 1 − p ′ 1 , the algorithm does not query I j , and the optimum strategy is to query I 1 and cascade if v j ∈ I 1 or C 1 ≤ w(R). Thus, the approximation ratio is at most w(R ′ ) w 1 + (1 − p j ) · w(R ′ ) + w 1 min(w 1 , w(R)) =: φ 1 , where z = w(R)/w 1 . Now consider the case when the algorithm queries I j before I 1 . With probability p j , the optimum strategy is to query I 1 and cascade, and the algorithm queries all intervals; also, if v 1 ∈ I j , then C 1 ≥ w 1 + w j . With probability 1 − p j , the algorithm does not query I 1 ; if v 1 ∈ I j , then the optimum is to query R only, as w(R ′ ) ≤ w 1 /3 (as discussed in the previous paragraph), otherwise the optimum is the minimum between querying I 1 and cascading or querying R only. Therefore, the approximation ratio is at most w(R) min(w 1 , w(R)) =: φ j . (9) which is maximized when p ′ 1 = 4 − 2 42/13 and the maximum is 17 − 2 182/3 < 1.4223. Case 3.2, w 1 > w(R). Note that z ∈ (0, 1), where z = w(R)/w 1 . Recalling that w(R ′ ) ≤ w(R)/4 and w(R ′ ) ≤ w j /3, we have w(R ′ ) < w 1 /4, w(R ′ ) < (w 1 + w j )/7, and (w(R ′ ) + w 1 )/ min(w 1 , w(R)) = (w(R ′ ) + w 1 )/w(R) ≤ 1/z + 1/4. In this case, Equation (8) is at most which is a function of z that is non-increasing for any fixed value of p ′ 1 , p j , since p j ≤ 1. On its turn, Equation (9) is at most (using w(R)/ min(w 1 , w(R)) = 1) If p j = 0 then this is optimal, and when p ′ 1 = 1 it can be bounded by 8/7. Otherwise we have a function of z that is increasing for any fixed value of p ′ 1 , p j , since p ′ 1 ∈ [0, 1) and p j ∈ (0, 1]. Since one function is non-increasing and the other is increasing, their minimum is maximized when they are equal, which happens when and Equation (13) then becomes (4 − 3z(1 − p ′ 1 ))(p ′ 1 + 7z(1 − p ′ 1 )) 28(1 − z(1 − z)(1 − p ′ 1 )) + 1 =:φ(p ′ 1 , z).
Note that the denominator of the first summand inφ(p ′ 1 , z) is minimized w.r.t. z at z = 1/2, hence is at most 21 + 7p ′ 1 , and the numerator is non-negative for z ∈ (0, 1). Taking factors 3(1 − p ′ 1 ) and 7(1 − p ′ 1 ) out of the first and second brackets (resp.) of the numerator and denoting a = For fixed p ′ 1 , the right-hand side of this inequality is a parabola with negative coefficient of z 2 , hence it is maximized when z = (a − b)/2, implying .
The approximation factor can be improved slightly by choosing a different parameter δ ∈ (0, 1/3] such that α ∈ [δ, 1 − δ]. Note that it does not work for δ ∈ (1/3, 1/2), since in this case we cannot build G ′ with w(R)/2 ≤ w(G ′ ) ≤ (1−δ)·w(R) simply by assuming that every interval in R has cost less than (1−δ)·w(R). Using the analysis of Case 1, this implies that a lower bound on the approximation that can be achieved by this strategy is 1 + √ 7/6 > 1.4409, even if not restricted by Cases 2 and 3.

Further Questions
It would be interesting to find out whether it is possible to implement our dynamic programming algorithm for the sorting problem more efficiently, e.g., in O(n 4 ) time. We could also try to extend our approach for sorting so as to handle a dynamic setting, e.g. as in [13], where some intervals can be inserted/deleted from the initial set; updating the dynamic program should be faster than building it again from scratch.
The main question that we leave open regards the complexity of finding the best decision tree for the minimum problem. It has proved non-trivial to obtain either a negative or positive result. It could also be promising to look for better approximation algorithms for particular cases, e.g. if query costs and probability distributions are uniform.
If it is NP-hard to find the best decision tree for the minimum problem, then the same applies to the stochastic versions of the problem of finding the k-th smallest value (the generalized median problem) [22,33] and the minimum spanning tree problem with uncertainty on edge weights [17,20,38]. This holds because the minimum problem is a particular case of both: for the k-th smallest value problem it is the case with k = 1; for the minimum spaning tree problem, if we have two vertices connected by multiple edges, then we want to identify the edge of minimum weight. It would be interesting to find out whether it is possible to devise polynomial-time algorithms for those problems with better approximation guarantees than the respective best results for the adaptive online problem with adversarial inputs, as we did for the minimum problem. We believe those problems would require different techniques to the ones we developed here, as they are more intricate.