We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Online purchasing under uncertainty.
- Authors
Frieze, Alan; Pegden, Wesley
- 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.
- Subjects
ONLINE shopping; RANDOM variables; HYPERGRAPHS; DIRECTED graphs; GEOMETRIC vertices
- Publication
Random Structures & Algorithms, 2018, Vol 53, Issue 2, p327
- ISSN
1042-9832
- Publication type
Article
- DOI
10.1002/rsa.20764