The secretary problem bound for posets with a fixed number of maximal elements
The secretary problem bound for posets with a fixed number of maximal elements
Let be a poset with maximal elements. Define
Secretary problem conjecture. There is an algorithm for the secretary problem on that is successful with probability at least .
The bound is proved in the source for posets of width and is expected to extend to all posets with maximal elements; it is not known from the supplied text whether the same algorithm works universally or another algorithm depending only on is required.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Bryn Garrod and Robert Morris, “The secretary problem on an unknown poset”, arXiv:1107.1379 (2012).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.