Online purchasing under uncertainty

DOI10.1002/RSA.20764MaRDI QIDQ4684832zbMATH OpenOpenAlexFDO

Authors Wesley Pegden, Alan Frieze

Publication date 25 September 2018

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1605.06072

zbMATH Keywords

combinatorial optimizationon-lineprobabilistic analysis

Mathematics Subject Classification ID

Hypergraphs (05C65) Random graphs (graph-theoretic aspects) (05C80) Combinatorial optimization (90C27)

Abstract: Suppose there is a collection $x_1,x_2,dots,x_N$ of independent uniform $[0,1]$ random variables, and a hypergraph $cF$ of emph{target structures} on the vertex set $1,dots,N$. We would like to buy 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,dots,N$ is the edge-set of some graph, 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.

Recommendations

• On the random 2-stage minimum spanning tree
• The price of information in combinatorial optimization
• On an Online Spanning Tree Problem in Randomly Weighted Graphs
• On the random 2-stage minimum spanning tree
• Algorithms for Secretary Problems on Graphs and Hypergraphs

Cited in

(6)

• Trustworthy online shopping with price impact
• Uncertain product availability in search markets
• Bracketing of purchases to manage size uncertainty: Should online retailers be worried?
• Fast construction on a restricted budget
• Some online maker-breaker games
• Uncertain switching costs and purchase decisions in electronic markets

This page was built for publication: Online purchasing under uncertainty

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4684832)