Online purchasing under uncertainty

Suppose there is a collection of independent uniform random variables, and a hypergraph of target structures on the vertex set . We would like to purchase a target structure at small cost, but we do not know all the costs x_i ahead of time. Instead, we inspect the random variables x_i one at a time, and after each inspection, choose to either keep the vertex i at cost x_i, or reject vertex i forever. In the present paper, we consider the case where is the edge‐set of a complete graph (or digraph), and the target structures are the spanning trees of a graph, spanning arborescences of a digraph, the paths between a fixed pair of vertices, perfect matchings, Hamilton cycles or the cliques of some fixed size.