Premium
Online purchasing under uncertainty
Author(s) -
Frieze Alan,
Pegden Wesley
Publication year - 2018
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20764
Subject(s) - combinatorics , digraph , vertex (graph theory) , mathematics , hypergraph , graph , discrete mathematics , random graph , spanning tree
Suppose there is a collectionx 1 , x 2 , … , x Nof 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 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 { 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.