3 ms·

What about needing to hire M candidates out of N applicants?

D_Alex 13y ago
And what about preferring the second best candidate to the average candidate... say if you interviewed 95% of applicants after rejecting the first 37%, and then you find a candidate who is almost, but not quite, as good as the very best one?
Cogito 13y ago
Without thinking about it too much... One solution might be to try and find the the best candidate after (N/M)/e candidates, rather than N/e candidates. Then find the best candidate after (N_remaining/(M-1))/e candidates. That is recurse, by finding one candidate at a time, and discarding less then N/e each time to ensure you get enough candidates.
hoonose 13y ago
There's a large body of work on variations of the secretary problem. The one I know of which is most relevant to your question is section 4 of the following: http://www.cs.cornell.edu/~rdk/papers/secArt4.pdf http://www.cs.cornell.edu/~rdk/papers/secArt4.pdf Section 6 is particularly interesting, where you're further restricted - you want to choose multiple secretaries, but there's certain constraints on the sets you can choose. For example, the secretaries might be edges in a graph, and you can't pick a subset of edges which would result in a cycle (this is a "graphic matroid," which is an example of a mathematical object known as a matroid). The reason why this formulation of the problem is interesting is because the best known algorithm is O(sqrt(log k))-competitive (where k is the rank of the matroid), whereas it is conjectured that an O(1)-competitive algorithm exists.
yogeshgirdhar 13y ago
I worked on a version on this problem where the goal is to maximize the probability of hiring all top M candidates while using a similar single threshold strategy. Here is a link to my paper: http://www.cim.mcgill.ca/~yogesh/publications/crv2009.pdf http://www.cim.mcgill.ca/~yogesh/publications/crv2009.pdf
imdsm 13y ago
I modified the one I worked on: http://jsbin.com/woyehiyu/1/edit http://jsbin.com/woyehiyu/1/edit (JavaScript, Console tabs. Click Run)

And what about preferring the second best candidate to the average candidate... say if you interviewed 95% of applicants after rejecting the first 37%, and then you find a candidate who is almost, but not quite, as good as the very best one?

Cogito 13y ago

Without thinking about it too much... One solution might be to try and find the the best candidate after (N/M)/e candidates, rather than N/e candidates. Then find the best candidate after (N_remaining/(M-1))/e candidates. That is recurse, by finding one candidate at a time, and discarding less then N/e each time to ensure you get enough candidates.

hoonose 13y ago

There's a large body of work on variations of the secretary problem. The one I know of which is most relevant to your question is section 4 of the following: http://www.cs.cornell.edu/~rdk/papers/secArt4.pdf http://www.cs.cornell.edu/~rdk/papers/secArt4.pdf Section 6 is particularly interesting, where you're further restricted - you want to choose multiple secretaries, but there's certain constraints on the sets you can choose. For example, the secretaries might be edges in a graph, and you can't pick a subset of edges which would result in a cycle (this is a "graphic matroid," which is an example of a mathematical object known as a matroid). The reason why this formulation of the problem is interesting is because the best known algorithm is O(sqrt(log k))-competitive (where k is the rank of the matroid), whereas it is conjectured that an O(1)-competitive algorithm exists.

yogeshgirdhar 13y ago

I worked on a version on this problem where the goal is to maximize the probability of hiring all top M candidates while using a similar single threshold strategy. Here is a link to my paper: http://www.cim.mcgill.ca/~yogesh/publications/crv2009.pdf http://www.cim.mcgill.ca/~yogesh/publications/crv2009.pdf

imdsm 13y ago

I modified the one I worked on: http://jsbin.com/woyehiyu/1/edit http://jsbin.com/woyehiyu/1/edit (JavaScript, Console tabs. Click Run)