We place $m$ balls at random (uniformly) inside $n^2$ urns arranged as a $n \times n$ square. Then we must choose $n$ urns, such that no two urns belong to the same row or column, with the objective of maximizing the count of selected balls.
This is a special case of the "random assignment problem".
There are many papers that study this problem, (asymptotics of the expected value, in general), especially for iid exponential variables - also for uniform, gaussian and some discrete distributions (eg: http://u.arizona.edu/~krokhmal/pdf/random-assignment-problems.pdf)
But in our case, the underlying distribution is a uniform multinomial, for which I've not found any result.
Alternatively, we might embrace the asymptotic equivalence of a multinomial to iid Poisson variables (Poissonization). But I've not found any results for iid Poisson variables either.
I'd like to know if some asymptotics for the expected value has been investigated.
Motivation and some preliminary results:
The problem is essentially equivalent to finding the minimum expected Hamming distance among random words of length $n$ over an alphabet of size $m$, if permutations are allowed. This was asked in MSE. I attemped a quite crude approximation, assimilating the Poisson to a Gaussian with same mean and variance, and using this reference. The approximation worked quite well, for $n\ge 3$.
