Duration problem with multiple exchanges
Mitsushi Tamaki, Krzysztof Szajowski, Charles Pearce · Numerical Algebra Control and Optimization · 2012
We treat a version of the multiple-choice secretary problem called themultiple-choice duration problem, in which the objective is to maximize the timeof possession of relatively best objects. It is shown that, for the $m$--choiceduration problem, there exists a sequence $(s_1,s_2,\ldots,s_m)$ of criticalnumbers such that, whenever there remain $k$ choices yet to be made, then theoptimal strategy immediately selects a relatively best object if it appears ator after time $s_k$ ($1\leq k\leq m$). We also exhibit an equivalence betweenthe duration problem and the classical best-choice secretary problem. A simplerecursive formula is given for calculating the critical numbers when the numberof objects tends to infinity. Extensions are made to models involving anacquisition or replacement cost.