Assigning Classes

[Dirk Koopman]

On 09/09/13 15:10, Raphael Mankin wrote:
> 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.
>

It also has similarities to rate minimisation problems in chemistry 
where one has several (say) gases, some energy, reactions happen and one 
has (essentially) guess what is likely to come out. Or alternatively: 
given what comes out and the starting proportions, how did it get there.

The NAG libraries have a raft of numercial algorithms for solving these 
sorts of problems - I always found the ones that used (cough) "Monte 
Carlo Methods" gave what seemed like the best answers and in (by far) 
the quickest time. I believe that after 30 odd years in the wilderness 
this type of algorithm is coming back into fashion as is worth a long.

Dirk