|No such thing as a small change|
Re^2: [OT] simple algorithm for assigning students to class sectionsby hossman (Prior)
|on Nov 30, 2004 at 18:50 UTC||Need Help??|
To do better than this simple lottery scheme, you must first decide what your optimality critera are. Do you want to maximize the number of first choices satisfied? The number of any choice satisfied?
See, that's part of my problem. I was asked to try and find a way to "get everyone in a section they can make" (ie: if they can't make it, they didn't list it in their prefrences) without any other critera. Which means a naive lottery like you described would work fine, assuming I just kept doing lots of iterations (using a different initial order of students) and picking the "best" based on which solution results in the fewest number of people left out of a section. But it seems to me that there are still two problems;
(I think the biggest part of my problem is that I'm not sure what the optimal criteria are ... which is why I'm hoping someone would have pointers to algorithms other people have used in problems like this -- where one side of the match only cares about quantity, not quality)UPDATE:
An idea just occured to me. I could score the solutions based on the sum of the "rank" of the choice each of section each student was assigned to. or to use an example, given the following prefrences...
A solution in which studentA was put in sec3 would get 3 points, because he listed 3 prefrences and got his first one. putting studentB in sec1 would only be worth 1 point, because he only listed one choice. Putting studentE in sec1 would be worth 1 point (because it was his last choice) but putting him in sec2 would be worth 4 points because it was his first (of 4) choice. if someone doesn't get placed in a section at all, the solution doesn't earn a point for them.
That seems like it would give priority to finding every one a section, but would be somewhat fair to people who were flexible, right?
The only problem I see right now, is that if there were two solutions that differed only in the order of processing studentB and studentE, and sec2,sec3,sec4 were already full and sec1 only had one spot left, then there would still be a tie between the solutions, even though studentE had been more flexible and (in my mind) deserves the slot more.
Maybe a solution in which someone doesn't get into any section should have the k*n points removed from it's score (where k is some small constant and n is hte number of prefrences the student listed?)