20090101
Secretary Problems: Weights and Discounts
Publication
Publication
The classical secretary problem studies the problem of selecting online an element (a “secretary”) with maximum value in a randomly ordered sequence. The difficulty lies in the fact that an element must be either selected or discarded upon its arrival, and this decision is irrevocable. Constantcompetitive algorithms are known for the classical secretary problems and several variants. We study the following two extensions of the secretary problem: In the discounted secretary problem, there is a timedependent “discount” factor $d(t)$, and the benefit derived from selecting an element/secretary e at time t is $d(t)v(e)$. For this problem with arbitrary (not necessarily decreasing) functions $d(t)$, we show a constantcompetitive algorithm when the expected optimum is known in advance. With no prior knowledge, we exhibit a lower bound and give a nearly matching $O(log n)$competitive algorithm. In the weighted secretary problem, up to K secretaries can be selected; when a secretary is selected (s)he must be irrevocably assigned to one of K positions, with position k having weight $w(k)$, and assigning object/secretary e to position k has benefit $w(k)v(e)$. The goal is to select secretaries and assign them to positions to maximize the sum of $w(k)v(e_k)$ where $e_k$ is the secretary assigned to position k. We give constantcompetitive algorithms for this problem. Most of these results can also be extended to the matroid secretary case for a large family of matroids with a constantfactor loss, and an O(log rank) loss for general matroids. These results are based on a reduction from various matroids to partition matroids which present a unified approach to many of the upper bounds of Babaioff et al. These problems have connections to online mechanism design. All our algorithms are monotone, and hence lead to truthful mechanisms for the corresponding online auction problems.
Additional Metadata  

Publisher  ACMSIAM 
Project  Discrete, interactive & algorithmic mathematics, algebra and number theory 
Conference  ACMSIAM Symposium on Discrete Algorithms 
Citation 
Babaioff, M, Dinitz, M, Gupta, A, Immorlica, N.S, & Talwar, K. (2009). Secretary Problems: Weights and Discounts. ACMSIAM.
