Partially ordered secretaries

Ragnar Freij (Chalmers University of Technology and University of Gothenburg)
Johan Wästlund (Chalmers University of Technology and University of Gothenburg)

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 at least $1/e$ for an arbitrary partial order.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 504-507

Publication Date: October 26, 2010

DOI: 10.1214/ECP.v15-1579

References

  1. Thomas Ferguson. Who solved the Secretary Problem? Statistical Science 4 (1989), 282-289. Math. Review 91k:01011
  2. Nicholas Georgiou, Malgorzata Kuchta, Michal Morayne and Jaroslaw Niemiec. On a universal best choice algorithm for partially ordered sets. Random Structures and Algorithms 32(3) (2008), 263-273. Math. Review 2009b:90120
  3. Jakub Kozik. Dynamic threshold strategy for universal best choice problem. DMTCS Proceedings, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (2010), 439-452. Math. Review number not available.
  4. Michal Morayne. Partial-order analogue of the secretary problem. The binary tree case. Discrete Mathematics 184(1-3) (1998), 165-181. Math. Review 99f:60086
  5. John Preater. The best-choice problem for partially ordered objects. Operations Research Letters 25 (1999), 187-190. Math. Review 2000g:90069
Bookmark and Share


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.