djk at tobit.co.uk
Mon Sep 9 15:34:03 BST 2013
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.
More information about the london.pm