Partially ordered secretaries

Ragnar Freij*, Johan Wästlund

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

17 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)504-507
Number of pages4
JournalELECTRONIC COMMUNICATIONS IN PROBABILITY
Volume15
Publication statusPublished - 2010
MoE publication typeA1 Journal article-refereed

Keywords

  • Best choice problem
  • Partial order
  • Secretary problem

Fingerprint Dive into the research topics of 'Partially ordered secretaries'. Together they form a unique fingerprint.

Cite this