0
$\begingroup$

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...)

Improve this question
$\endgroup$
5
  • $\begingroup$ This looks like a good question for cstheory.stackexchange.com $\endgroup$
    – Andrej Bauer
    Sep 23, 2011 at 11:49
  • $\begingroup$ 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. $\endgroup$
    – Andrej Bauer
    Sep 23, 2011 at 11:51
  • 3
    $\begingroup$ isn't this just stable marriage type of stuff? $\endgroup$
    – Suvrit
    Sep 23, 2011 at 11:51
  • $\begingroup$ 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). $\endgroup$
    – kaleidoscop
    Sep 23, 2011 at 12:31
  • 2
    $\begingroup$ By the way, cstheory is research level only. Like MO, not like Math.SE. $\endgroup$
    – Noah Snyder
    Sep 23, 2011 at 13:58

1 Answer 1

Reset to default
2
$\begingroup$

Are you looking for the stable marriage problem?

Improve this answer
$\endgroup$

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