I'm working on a project for my university in wich the students can choose their preferred seminars for the next semester.

My goal is it to allocate these weighted votes in an optimal way to the available seminars.

Here is some more information:

Each seminar can be selected from either : One B.Sc., one M.Sc. or Two B.Sc.

Each Student can cast exactly 10 votes with the priorities 1 to 4 for each vote.

I'm not an expert on math, so my simplest imaginable algorithm was this:

do 10000+ runthroughs{
  shuffle all the students;
  foreach student{
    take the student give him the, for him, best available seminar (greedy choice);
    deside on the priority of the vote(seminar) wich was given to him 
    what penalty is added to this shuffled students penalty(
       Priority 1 -> Penalty 1
       Priority 2 -> Penalty 2
       Priority 3 -> Penalty 3
       Priority 4 -> Penalty 5
       no allocation -> Penalty 10);
    save allocation with penalty;
print allocation with lowest penalty;

It works fine but only if the runthroughs are pretty high, so I was wondering if there is another algorithm which can better solve this problem, and is also optimal in the first try.

It was hard to describe my problem here, so you could imagine that I wasn't able to find a suitable solution for my problem on google etc.

I hope you could give me the name of an algorithm that fits my needs, or else you could write some down here.

Cheers, Felix

PS: Sorry for my english: I'm not a native speaker ;)

  • $\begingroup$ Hi Felix, for some specific values about your question: how many students are there; how many seminars are there; can students allocate more than one vote for each seminar; are students allowed to indicate a priority of one on each vote? $\endgroup$ Feb 28 '13 at 13:47
  • $\begingroup$ Hi: I went ahead and polished the text a bit. You can view the changes by clicking the edit timestamp. I hope you find them useful! I think you did a rather good job of presenting your question. $\endgroup$
    – rschwieb
    Feb 28 '13 at 14:06
  • $\begingroup$ Are the votes from a single student a sorted order? Such as: first choice vote is such and such (B.Sc. or whatever), second choice is ... Like a preference order? $\endgroup$
    – adam W
    Feb 28 '13 at 15:02
  • $\begingroup$ Last semester in the first test run there were about 80 Students an about 40 seminars. Half auf the seminars were applicable for 2 B.Sc. Students so there were about 20-30 Students without a seminar at the end. Students have to vote 10 different seminars, but different students are able to vote for the same seminar. If the seminar is for two B.Sc students two B.Sc students could be allocated. The Votes are in a mysql table in the format (StudentId, SeminarID, Priority, ...additional system information like semester etc.) so i would think that they are "sorted"? $\endgroup$
    – FMK
    Feb 28 '13 at 15:55
  • $\begingroup$ I ask because I believe your question is a matching problem, and is a bipartite graph. Graph theory is not my specialty at all, but I think you would do well to re-tag the question as such. $\endgroup$
    – adam W
    Feb 28 '13 at 18:14

It might be the case that this can be posed as a stable matching problem. If so, then the Gale-Shapley algorithm may be of use.

You can set the partite sets to be $A$ and $B$. Where $A$ is the set of students and $B$ is the set of seminars (if multiple students are allowed you can just make copies of the vertices, thus turning $B$ into a multiset).

I hope this helps.

  • $\begingroup$ This looks like what i've been looking for. I'll try to work my way through the algorithm to get it working thanks :) $\endgroup$
    – FMK
    Mar 5 '13 at 11:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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