Minimizing the cost of using the Hiring Problem_问答_开发者

I have gone through one of the books of algorithm and have found a problem named Hiring Problem. Here is the situation:

I have to conduct an interview for hiring candidates for my company. I am not personally able to conduct the interview, as I have failed to do so. So I have hired an employment agency to help with hiring the candidate. Each day the agency will send me a candidate from among n candidates. Algorithm for this will be:

**Algo Hiring Candidate(n)**  
best=0 // The candidate with the least quality  
for i=1 to n  
If the candidate is better than the best valued candidate we should hire him  
Best=candidate[i]  
return i;

But here, the interview cost will be always calculated as we have to take the interview of each candidate. So we have to concentrate on how to minimize the hiring cost.

Total cost will be O(interv开发者_StackOverflowiew cost and hiring cost)

I have gone through many observations, such as the agency will send the candidate randomly and in the worst case we have to hire all the candidates, then the hiring cost will be higher as each candidate came in an order of increasing quality.

But practically this is not possible, as it is never possible that all the candidates will come always in increasing order. They should come in a random order.

I have taken many observations but I am really not able to minimize the hiring cost. Can someone help me out through this problem.

I think that this is an example of the Secretary Problem.

Your problem is indeed (a variant of) the hiring problem, which itself is a multi-objective version of the secretary problem.

In the latter, one has a bunch of n candidates arriving in some arbitrary order of quality, and has to take an instant decision (accept the candidate or reject without any second chance). As one sees more and more candidates, one gets a better picture of the overall quality of candidates, but the odds are increasing that the best ones belong to the past (Actually, this problem should be called the "Dating game" or the "Picky Single" if you ask me...). The goal is then to find a strategy which maximizes the probability of getting the best one. This goal can be achieved by looking at n/e out of the n candidates, and then pick the next candidate whose quality exceeds that of the n/e "training set" (first candidates).

Slightly contrasting, the hiring problem aims at selecting many good candidates. As described nicely in the introduction (page 3) of Dr Ahmed Mohamed Helmi Mohamed Elsadek's PhD manuscript, there are two contradictory objectives underlying the hiring problem:

Optimize the quality of hired candidates
Maximize the number of hired candidates

Note that if only 1. is considered, then the best strategy is very likely the same as for the secretary problem. If only 2. is considered, then simply accept everyone without worrying about their skills. When both are taken into account, one has to merge these two objectives into some sort of optimal tradeoffs, and there is more than one optimal strategy. The above-mentioned thesis has a bunch of nicely explained strategies (cf Preater's “better than-average rule, Krieger, Pollak and Samuel-Cahn's “p-percentile rules”...).

Now, your problem seems slightly different (one pays to see a candidate, and one pays to hire her/him), but I believe that reading the thesis introduction would help you formalize which, of the possible tradeoffs (between number of retained candidates, quality of retained candidates and number of interview), seems best as an objective function and, in turn, which of the strategies seems the most promising.