Home | Contents | Submissions, editors, etc. | Login | Search | EJP
 Electronic Communications in Probability > Vol. 15(2010) > Paper 45 open journal systems 


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: PDF

Pages: 504-507

Published on: October 26, 2010
Bibliography
  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
















Research
Support Tool
Capture Cite
View Metadata
Printer Friendly
Context
Author Address
Action
Email Author
Email Others


Home | Contents | Submissions, editors, etc. | Login | Search | EJP

Electronic Communications in Probability. ISSN: 1083-589X