Partially ordered secretaries

• 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.

Ämnesord

NATURVETENSKAP  -- Matematik -- Sannolikhetsteori och statistik (hsv//swe)

NATURAL SCIENCES  -- Mathematics -- Probability Theory and Statistics (hsv//eng)

NATURVETENSKAP  -- Matematik -- Beräkningsmatematik (hsv//swe)

NATURAL SCIENCES  -- Mathematics -- Computational Mathematics (hsv//eng)

NATURVETENSKAP  -- Matematik -- Diskret matematik (hsv//swe)

NATURAL SCIENCES  -- Mathematics -- Discrete Mathematics (hsv//eng)

Nyckelord

Secretary problem

Best choice problem

Partial order.

Best choice problem

Publikations- och innehållstyp

ref (ämneskategori)

art (ämneskategori)