Details

Autor(en) / Beteiligte

• Woryna, Adam

Titel

The solution of a generalized secretary problem via analytic expressions

Ist Teil von

• Journal of combinatorial optimization, 2017-05, Vol.33 (4), p.1469-1491

Ort / Verlag

New York: Springer US

Erscheinungsjahr

2017

Link zum Volltext

Quelle

SpringerLink (Online service)

Beschreibungen/Notizen

• Given integers 1 ≤ k < n , the Gusein-Zade version of a generalized secretary problem is to choose one of the k best of n candidates for a secretary, which are interviewing in random order. The stopping rule in the selection is based only on the relative ranks of the successive arrivals. It is known that the best policy can be described by a non-decreasing sequence ( s 1 , … , s k ) of integers with l ≤ s l < n for every 1 ≤ l ≤ k , and conversely, any such a sequence determines the general structure of the best policy. We found a finite analytic expression for the probability of success when using the optimal policy with a sequence ( s 1 , … , s k ) . We also study the problem of the construction of the optimal sequence, i.e. a sequence which maximizes the corresponding probability of success. We discovered finite analytic expressions which enable to calculate the elements s l of an optimal sequence one by one, from l = k to l = 1 . Until now, such expressions were derived separately, and only for the values k ≤ 3 .