The Taub Faculty of Computer Science Events and Talks

The Classical Secretary Problem was introduced during the 60's of the 20-th century (nobody is sure exactly when). Since its introduction, many variants of the problem have been proposed and researched. In the classical secretary problem, and many of its variant, the input (which is a set of secretaries, or elements) arrives in a random order. We applied to the secretary problem a simple observation which states that the random order of the input can be generated by independently choosing a random continuous arrival time for each secretary. Surprisingly, this simple observation enables us to improve the competitive ratio of several known and studied variants of the secretary problem. In addition, in some cases the proofs we provide assuming random arrival times are shorter and simpler in comparison to existing proofs. In the talk, I will describe the variants for which we provide the improvements, and will present our algorithm for one of these variants. The talk is self contained. No previous knowledge in submodular optimization or online algorithms is assumed.

Based on a joint work with Seffi Naor and Roy Schwartz.