Online purchasing under uncertainty. Issue 2 (29th January 2018) - Frieze, Alan; Pegden, Wesley
Abstract: Suppose there is a collection x 1, x 2, …, x N of independent uniform [ 0, 1 ] random variables, and a hypergraph F of target structures on the vertex set 1, …, N . We would like to purchase a target structure at small cost, but we do not know all the costs xi ahead of time. Instead, we inspect the random variables xi one at a time, and after each inspection, choose to either keep the vertex i at cost xi, or reject vertex i forever. In the present paper, we consider the case where 1, …, N 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.