The secretary problem on an unknown poset

Details The secretary problem on an unknown poset The secretary problem on an unknown poset

2011-07-07

arxiv.org/abs/1107.1379v1

Mathematics

Combinatorics

22 pages, 3 figures

Scientific paper

We consider generalizations of the classical secretary problem, also known as the problem of optimal choice, to posets where the only information we have is the size of the poset and the number of maximal elements. We show that, given this information, there is an algorithm that is successful with probability at least $\frac{1}{e}$. We conjecture that if there are $k$ maximal elements and $k \geq 2$ then this can be improved to $\sqrt[k-1]{\frac{1}{k}}$, and prove this conjecture for posets of width $k$. We also show that no better bound is possible.

Affiliated with

Also associated with

No associations

Rating

The secretary problem on an unknown poset does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The secretary problem on an unknown poset, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The secretary problem on an unknown poset will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-416971