Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Hi!

I am interested in an algorithmic question. I'm not at all a specialist but I'm interested in this for very pragmatic reasons that you will understand. Maybe the problem is well known.

In a recruitment procedure, some candidates apply to several positions at different Universities. Each university ranks the candidates. Each candidate indicates its ordered preference list.

First question: What is an optimal solution of this problem?

Second question: Are there algorithms that find optimal solutions?

Let me give you an example of the bad things that can happen

Assume there are 2 positions and 2 candidates only. Each candidate is ranked second at its prefered university. Then the algorithm should give to each one its prefered university (although the candidate is ranked second).

Here the solution looks quite easy, but if there are 100 positions and a 100 candidates with each one a different "first choice", and if each candidate is ranked 100th at the university he/she prefers, then the algorithm should be able to figure it out and give every candidate its first choice.

I know the ministry of education has one algorithm, but I don't know if it is optimal (it actually relies on the fact that usually everyone has more or less the same "first choice" and so the best candidates choose, then the seconds, etc...)

share|improve this question

closed as too localized by Felipe Voloch, Suvrit, Ben Webster Sep 23 '11 at 13:54

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

    
This looks like a good question for cstheory.stackexchange.com –  Andrej Bauer Sep 23 '11 at 11:49
    
Aren't there some data missing? It seems obvious that each candidate gets to choose just one university, but can a university take in more candidates? In your example, we cannot know what happens until we hear the preferences of the candidates that were ranked first by the universities. –  Andrej Bauer Sep 23 '11 at 11:51
3  
isn't this just stable marriage type of stuff? –  Suvrit Sep 23 '11 at 11:51
    
Yes it is, thanks for the pointer (maybe I should have indicated that I wanted a reference instead of saying i'm not a specialist, so as not to be voted off). –  kaleidoscop Sep 23 '11 at 12:31
2  
By the way, cstheory is research level only. Like MO, not like Math.SE. –  Noah Snyder Sep 23 '11 at 13:58

1 Answer 1

Are you looking for the stable marriage problem?

share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.