1
$\begingroup$

I'm trying to develop an algorithm in Ruby to allocate one university to each student of a list. As opposed to Gale-Shapley algorithm, universities do no choose nor rank students; only students make a 6-wish ordered list.

  • There are 336 students
  • There are 151 cities, each with an available number of places between 1 & 6

I think this boils down to computing a minimum sum of 'distances', a student's distance being the rank of the university he was attributed (in his ordered list). E.g: if a student is given his first choice, then his 'distance' is 0. If a student is given his last choice, then his 'distance' is 5.

I see 2 possibilities:

  • brute-force to compute all the possibilities and find the one with the minimum sum of distances. But I think it would take too much time/very bad performance & complexity.
  • determine criterion beforehand to allocate universities. E.g: we start by giving all non-disputed 1st choice cities to students (e.g if 4 students put 'Paris' as their first choice and Paris has more than 4 seats, we give these 4 students the Paris university). And then we can do the same all the way down to the 6th choices. But this will not give a university to all students, so we then need to find another criteria (or several other criterion) to allocate a university to each of the remaining students. There is another downside of this method: the allocation will depend on the criterion chosen and the algo will maybe not give the best output (minimum of sum of distances).

My questions are:

  • do I need to use brute-force to find the optimal solution?
  • if not, what are the 'best' criterion to allocate universities in this algorithm? ('best' meaning it will allow me to end up with the optimal solution, or if it can't, at least with a pretty good solution overall)

NB:

  • I'm a beginner in Ruby & algo, I've read posts on different websites with a lot of theoretical knowledge required but that didn't help me, so if you could vulgarize that would be awesome :)
  • I originally posted my question on StackOverflow
  • For now, I'm not considering weighing choices non-linearly (e.g. a last choice 'costs' 10 instead of 5), as I think it will be easy to add once I know the right way to proceed
Improve this question
$\endgroup$
4
  • $\begingroup$ Please do not post the same question on multiple sites. Thank you. $\endgroup$
    – D.W. ♦
    Commented Jun 27, 2021 at 21:31
  • $\begingroup$ I was advised to do so, but I won't next time. Thanks $\endgroup$
    – eleove
    Commented Jun 28, 2021 at 7:51
  • $\begingroup$ I’m voting to close this question because the OP is interested mainly in solutions implementable in Ruby. $\endgroup$
    – Yuval Filmus
    Commented Jun 28, 2021 at 9:35
  • $\begingroup$ @eleove, I understand - from your perspective, you were just following what advice others were giving. My guess is they were just trying to help, but not everyone is familiar with this rule. Now you know about it. Also, I do want to highlight that, while I can see how it might have looked that way, I don't think they were actually recommending you cross-post -- they were trying to recommend a better site, which is consistent with the advice to delete your question there before posting here if you post it on the wrong site. $\endgroup$
    – D.W. ♦
    Commented Jun 28, 2021 at 19:52

1 Answer 1

Reset to default
1
$\begingroup$

You can use the assignment problem.

Construct a bipartite graph, where one side corresponds to students, and the other side corresponds to spots in cities: if a city has $n$ spots, there will be $n$ vertices corresponding to the city. If student $x$ is interested in city $y$, connect $x$ to all spots of $y$ with an edge whose weight corresponds to the "distance". Now compute a maximum weight perfect matching (or a maximum weight matching, if you want to allow students to be unmatched).

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thanks a lot but I'm looking for a practical way to implement it (in Ruby ideally), as I'm not familiar with topics like vertices, etc. $\endgroup$
    – eleove
    Commented Jun 28, 2021 at 7:51
  • $\begingroup$ You cannot solve an algorithmic problem if you're not prepared to use algorithms. $\endgroup$
    – Yuval Filmus
    Commented Jun 28, 2021 at 9:34
  • $\begingroup$ You're right @YuvalFilmus so I watched this 50-min (great) video on bi-partite matching but it doesn't apply to my case as: - it is for 1 student at max per job (I have Cities with like 6 available seats) - it doesn't take into consideration the ranking of choices - 1 student may not have a job at the end $\endgroup$
    – eleove
    Commented Jun 30, 2021 at 12:30
  • $\begingroup$ Your problem reduces to the weighted version of bipartite matching. This is what I explain in the answer. You can handle cities with several available seats by splitting them to several equivalent cities. You can allow unmatched students by adding the appropriate number of dummy cities, connected to all students with zero weight edges. $\endgroup$
    – Yuval Filmus
    Commented Jun 30, 2021 at 14:36
  • $\begingroup$ It is likely that someone wrote a Ruby library that solves the assignment problem, so you don’t even have to program any algorithm. $\endgroup$
    – Yuval Filmus
    Commented Jun 30, 2021 at 14:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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