Assigning Classes

[Raphael Mankin]

This is a classic variation of the transportation problem.

If you can assign (different) costs to being in the wrong class and zero
cost to being in the right class then the Hungarian Algorithm will do
the job.

The standard version of the algorithm has quartic time complexity, but
there is a version due to Wright(?) at Lancaster University that is
quadratic. Both versions have quadratic space complexity. I programmed
it about 20 years ago but I cannot now give you any references. Search
the literature.

On Mon, 2013-09-09 at 09:16 -0400, Mark Fowler wrote:
> On Monday, 9 September 2013 at 08:45, Dave Cross wrote:
> > I have offered to help a friend[1] solve what sounds like an 
> > interesting problem.
> 
> No idea on the literature, but here's my two pence worth:
>  
> I'd start by putting everyone in their favourite choice of classes, and seeing how "bad" that is.  I assume since you're asking the question that's not a possible solution.
> 
> How feasible is it to randomly select students and move them and see how that works?  I ask because this is what we'd do before we had computers, but with a computer you could do this a million times a second and try out all the possibilities (it's key to limit the number of moves to narrow the problem space so we don't have to wait for the heat death of the universe first - hence the putting everyone in the "optimal but broken" place to start with.)  You'd need a "unhappiness" score for a student which could be computed from the distance they are from their "ideal" courses.  You might want to look at adding some sort of power rule to the distance too, since you'd probably be better off with a bunch of slightly unhappy students verses all happy but one very screwed over student.  Obviously junk any 'solution' that doesn't meet your class criteria.
> 
> Mark.
> 
>