Look up the Hungarian algorithm. It's along the same lines. This is really an "assignment problem." There are others, but I can't remember. I think you should be able to get this to O(n^3) or O(n^2). The product is really trivial, your just looking for the N largest numbers not in the same row or column.