CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Partially ordered secretaries

Ragnar Freij (Institutionen för matematiska vetenskaper) ; Johan Wästlund (Institutionen för matematiska vetenskaper, matematik)
Electronic Communications in Probability (1083-589X). Vol. 15 (2010), p. 504-507.
[Artikel, refereegranskad vetenskaplig]

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.

Nyckelord: Secretary problem, Best choice problem, Partial order.

Denna post skapades 2010-12-01. Senast ändrad 2016-07-26.
CPL Pubid: 129918


Läs direkt!

Lokal fulltext (fritt tillgänglig)

Institutioner (Chalmers)

Institutionen för matematiska vetenskaperInstitutionen för matematiska vetenskaper (GU)
Institutionen för matematiska vetenskaper, matematik (2005-2016)


Diskret matematik
Optimeringslära, systemteori
Matematisk statistik

Chalmers infrastruktur

Relaterade publikationer

Denna publikation ingår i:

Topics in algorithmic, enumerative and geometric combinatorics