Online purchasing under uncertainty. Issue 2 (29th January 2018)

• Record Type: Journal Article
• Authors: Frieze, Alan; Pegden, Wesley
• Is Part Of: Random structures & algorithms. Volume 53:Issue 2(2018)
• Page Start: 327
• Page End: 351
• Publication Date: 2018-01-29
• Subjects: combinatorial optimization -- on‐line -- probabilistic analysis; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20764
• Languages: English
• ISSNs: 1042-9832

Abstract

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.