Heuristic algorithms for the dense assignment problem
This paper has a painfully detailed table on what you can achieve using (currently known) deterministic, randomized and $\epsilon$-approximation algorithms. To summarize, for the bipartite case (all assuming integer weights bounded by $N$):


Deterministic time $O(n^2 \sqrt n \log N)$.
Randomized $O(n^{2.373} N)$.
$(1 - \epsilon)$-approximation in $O(n^2 \epsilon^{-1} \log N)$.


These algorithms are mostly very complex and go through $LP$ formulations. It is unlikely that any of them are truly what you're looking for. Also, regarding their use of space, I am not sure, but you can follow the papers for the different algorithms and see for yourself, if you can make them work in less space. (By the way, isn't your cost function already using quadratic space?)

If you want a heuristic with no provable guarantees, then I recommend the simple local search. You basically start with some random permutation (this is a feasible assignment, since your bipartite graph is complete) and make random swaps that improve the cost. If you do many such searches, you get a good solution more often then not. You can make the whole thing run in $O(t (n + s))$ time and linear space, if you do $t$ searches (from random permutations), each for $s$ steps. Choose $t, s$ to trade-off quality of the solution with complexity.