NDLI: Analysis of the Strategy “Hiring Above the $$m$$ -th Best Candidate”

Content Provider	Springer Nature Link
Author	Helmi, Ahmed Martínez, Conrado Panholzer, Alois
Copyright Year	2014
Abstract	The hiring problem is a simple model for on-line decision-making, inspired by the well-known and time-honored secretary problem (see, for instance, the surveys of Freeman Int Stat 51:189–206, 1983 or Samuels Handbook of sequential analysis, 1991). In the combinatorial model of the hiring problem (Archibald and Martínez Proc. of the 21st Int. Col. on Formal Power Series and Algebraic Combinatorics (FPSAC), 2009), there is a sequence of candidates of unknown length, and we can rank all candidates from best to worst without ties; all orders are equally likely. Thus any finite prefix of the sequence of candidates can be modeled as a random permutation. Candidates come one after another, and a decision must be taken immediately either to hire or to discard the current candidate, based on her relative rank among all candidates seen so far. In this paper we analyze in depth the strategy hiring above the $$m$$ -th best candidate (or hiring above the $$m$$ -th best, for short), formally introduced by Archibald and Martínez (Proc. of the 21st Int. Col. on Formal Power Series and Algebraic Combinatorics (FPSAC), 2009). This hiring strategy hires the first $$m$$ candidates in the sequence whatever their relative ranks, then any further candidate is hired if her relative rank is better than the $$m$$ -th best candidate seen so far. The close connection of this hiring strategy to the notion of records in sequences and permutations is quite evident; records and their generalizations (namely, $$m$$ -records) have been throughly studied in the literature (see, for instance, the book of Arnold et al. Records, Wiley Series in Probability and Mathematical Statistics, 1998), and we explore here that relationship. We also discuss the relationship between this hiring strategy and the seating plan $$(0,m)$$ for the well-known Chinese restaurant process (Pitman Combinatorial stochastic processes, 2006). We analyze in this paper several random variables (we also call them hiring parameters) that give us an accurate description of the main probabilistic features of “hiring above the $$m$$ -th best”, from the point of view of the hiring rate (number of hired candidates, waiting time to hire a certain number of candidates, time between consecutive hirings,...) and also of the quality of the hired staff (rank of the last hired candidate, best discarded candidate,...). We are able to obtain the exact and asymptotic probability distributions for the most fundamental parameter, namely, the number of hired candidates, and also for most of the other parameters. Another novel quantity that we analyze here is the number of replacements, a quantity naturally arising when we consider “hiring above the $$m$$ -th best” endowed with a replacement mechanism: that is, an incoming candidate can be: (1) hired anew, because the candidate is among the $$m$$ best seen so far, (2) hired to replace some previously hired worse candidate, or (3) discarded.
Starting Page	267
Ending Page	300
Page Count	34
File Format	PDF
ISSN	01784617
Journal	Algorithmica
Volume Number	70
Issue Number	2
e-ISSN	14320541
Language	English
Publisher	Springer US
Publisher Date	2014-06-06
Publisher Place	Boston
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Hiring problem Secretary problem On-line decision problems Records Permutation Chinese restaurant process Algorithm Analysis and Problem Complexity Theory of Computation Mathematics of Computing Algorithms Computer Systems Organization and Communication Networks Data Structures, Cryptology and Information Theory
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Computer Science Applications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Analysis of the “Hiring Above the Median” Selection Strategy for the Hiring Problem

On Variants of the Matroid Secretary Problem

Permutation Routing on Reconfigurable Meshes

The Longest Path Problem Is Polynomial on Cocomparability Graphs

Bounded Space On-Line Bin Packing: Best Is Better than First

Competitive Weighted Matching in Transversal Matroids

Permutation Betting Markets: Singleton Betting with Extra Information

Fully Dynamic Algorithm for Recognition and Modular Decomposition of Permutation Graphs

Separation Dimension of Graphs and Hypergraphs

Analysis of the Strategy “Hiring Above the $$m$$ -th Best Candidate”

Similar Documents

Analysis of the “Hiring Above the Median” Selection Strategy for the Hiring Problem

On Variants of the Matroid Secretary Problem

Permutation Routing on Reconfigurable Meshes

The Longest Path Problem Is Polynomial on Cocomparability Graphs

Bounded Space On-Line Bin Packing: Best Is Better than First

Competitive Weighted Matching in Transversal Matroids

Permutation Betting Markets: Singleton Betting with Extra Information

Fully Dynamic Algorithm for Recognition and Modular Decomposition of Permutation Graphs

Separation Dimension of Graphs and Hypergraphs

Analysis of the Strategy “Hiring Above the $$m$$ -th Best Candidate”