2012 | OriginalPaper | Buchkapitel
Hiring above the m-th Best Candidate: A Generalization of Records in Permutations
verfasst von : Ahmed Helmi, Conrado Martínez, Alois Panholzer
Erschienen in: LATIN 2012: Theoretical Informatics
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The
hiring problem
is a simple model of on-line decision-making under uncertainty. It is closely related to the well-known
secretary problem
, formally introduced in the early sixties. Broder et al. (2008) introduced the
hiring problem
as an extension of the secretary problem. Instead of selecting only one candidate, we are looking for selecting (hiring) many candidates to grow up a small company. In this context, a hiring strategy should meet two demands: to hire candidates at some reasonable rate and to improve the average quality of the hired staff. Soon afterwards, Archibald and Martínez (2009) introduced a discrete model of the hiring problem where candidates seen so far could be ranked from best to worst without the need to know their absolute quality scores. Hence the sequence of candidates could be modeled as a random permutation. Two general families of hiring strategies were introduced:
hiring above the m-th best candidate
and
hiring in the top P
%
quantile
(for instance,
P
= 50 is hiring above the median). In this paper we consider only hiring above the
m
-th best candidate. We introduce new hiring parameters that describe the dynamics of the hiring process, like the
distance between the last two hirings
, and the quality of the hired staff, like the
score of the best discarded candidate
. While Archibald and Martínez made systematic use of analytic combinatorics techniques (Flajolet, Sedgewick, 2008) in their analysis, we use here a different approach to study the various hiring parameters associated to the hiring process. We are able to obtain explicit formulas for the probability distribution or the probability generating function of the random variables of interest in a rather direct way. The explicit nature of our results also allows a very detailed study of their asymptotic behaviour. Adding our new results to those of Archibald and Martínez leads to a very precise quantitative characterization of the hiring above the
m
-th best candidate strategy. This might prove very useful in applications of the hiring process, e.g., in data stream algorithms.