Let $A =(a_{ij})$ be a $m \times n$ matrix with nonnegative integer entries bounded above by $k$. To find the set of entries of $A$ in a non-attacking rook placement such that the sum $S$ of them is maximal amounts to solving the linear assignment problem (for the matrix $-A$). Letting the latter maximal sum be $S_{\text{max}}$, I was thinking of the following question: Clearly $S_1 = \sum\limits_{i,j}a_{ij} >S_{\text{max}}$, however is this the best we can do, i.e. is there another inequality that gives more information somehow, i.e $f(S_1) \geq g(S_{\text{max}})$, for some functions $f,g$ (maybe even involving $k$)?


1 Answer 1


Because you can select at most one entry per row, $$S_\max \le \sum_i \max_j a_{ij}$$

Because you can select at most one entry per column, $$S_\max \le \sum_j \max_i a_{ij}$$

And these together imply a weak but simple bound that does not involve $a_{ij}$: $$S_\max \le k \min(m,n)$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.