# The duration problem with multiple exchanges

Charles E.M. Pearce, Krzysztof Szajowski, Mitsushi Tamaki

Arxiv ID: 0812.3765•Last updated: 11/23/2020

We treat a version of the multiple-choice secretary problem called the
multiple-choice duration problem, in which the objective is to maximize the
time of possession of relatively best objects. It is shown that, for the
$m$--choice duration problem, there exists a sequence (s1,s2,...,sm) of
critical numbers such that, whenever there remain k choices yet to be made,
then the optimal strategy immediately selects a relatively best object if it
appears at or after time $s_k$ ($1\leq k\leq m$). We also exhibit an
equivalence between the duration problem and the classical best-choice
secretary problem. A simple recursive formula is given for calculating the
critical numbers when the number of objects tends to infinity. Extensions are
made to models involving an acquisition or replacement cost.

#### PaperStudio AI Chat

I'm your research assistant! Ask me anything about this paper.