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

$\begingroup$
$\endgroup$

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)$$