  We study a generalization of the secretary problem, where decisions do not
have to be made immediately upon candidates' arrivals. After arriving, each
candidate stays in the system for some (random) amount of time and then leaves,
whereupon the algorithm has to decide irrevocably whether to select this
candidate or not. The goal is to maximize the probability of selecting the best
candidate overall. We assume that the arrival and waiting times are drawn from
known distributions.
  Our first main result is a characterization of the optimal policy for this
setting. We show that when deciding whether to select a candidate it suffices
to know only the time and the number of candidates that have arrived so far.
Furthermore, the policy is monotone non-decreasing in the number of candidates
seen so far, and, under certain natural conditions, monotone non-increasing in
the time. Our second main result is proving that when the number of candidates
is large, a single threshold policy is almost optimal.
