pith. sign in

arxiv: 1008.3310 · v2 · pith:WA7AN55Anew · submitted 2010-08-19 · 🧮 math.OC · cs.DS· math.PR

Partially ordered secretaries

classification 🧮 math.OC cs.DSmath.PR
keywords orderselectorelementsexposedorderedpartialpartiallyprobability
0
0 comments X
read the original abstract

The elements of a finite nonempty partially ordered set are exposed at independent uniform times in $[0,1]$ to a selector who, at any given time, can see the structure of the induced partial order on the exposed elements. The selector's task is to choose online a maximal element. This generalizes the classical linear order secretary problem, for which it is known that the selector can succeed with probability $1/e$ and that this is best possible. We describe a strategy for the general problem that achieves success probability $1/e$ for an arbitrary partial order.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.