Timezone: »

Hiring Under Uncertainty
Manish Purohit · Sreenivas Gollapudi · Manish Raghavan

Wed Jun 12 06:30 PM -- 09:00 PM (PDT) @ Pacific Ballroom #170
In this paper we introduce the hiring under uncertainty problem to model the questions faced by hiring committees in large enterprises and universities alike. Given a set of $n$ eligible candidates, the decision maker needs to choose the sequence of candidates to make offers so as to hire the $k$ best candidates. However, candidates may choose to reject an offer (for instance, due to a competing offer) and the decision maker has a time limit by which all positions must be filled. Given an estimate of the probabilities of acceptance for each candidate, the hiring under uncertainty problem is to design a strategy of making offers so that the total expected value of all candidates hired by the time limit is maximized. We provide a 2-approximation algorithm for the setting where offers must be made in sequence, an 8-approximation when offers may be made in parallel, and a 10-approximation for the more general stochastic knapsack setting with finite probes.

Author Information

Manish Purohit (Google Research)
Sreenivas Gollapudi (Google Research)
Manish Raghavan (Cornell)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors