News for hackers. Stuff that matters.
Re:Secretary Problem by vehementi on Monday March 03, 2014 @11:14PM (#7338420)
What about needing to hire M candidates out of N applicants?
Re:Secretary Problem by hoonose on Tuesday March 04, 2014 @12:41AM (#7338701)
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

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.

Re:Secretary Problem by yogeshgirdhar on Tuesday March 04, 2014 @02:38AM (#7338984)
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

Re:Secretary Problem by D_Alex on Monday March 03, 2014 @11:31PM (#7338468)
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?
Re:Secretary Problem by Cogito on Monday March 03, 2014 @11:34PM (#7338482)
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.

Re:Secretary Problem by imdsm on Tuesday March 04, 2014 @09:00AM (#7340159)
I modified the one I worked on:

http://jsbin.com/woyehiyu/1/edit

(JavaScript, Console tabs. Click Run)