# Efficient algorithm for slightly generalized attribution problem

I have what I believe is an attribution problem: Given an $m \times n$ matrix, I need to select $p = \min\{m,n\}$ elements maximizing their sum such that they do not share a row or column.

More formally, I have the following linear optimization problem to solve:

\begin{align} \max \sum x_{ij} m_{ij} \\ \text{subject to} \\ \begin{cases} \sum_i x_{ij} \le 1 \\ \sum_j x_{ij} \le 1 \\ x_{ij} \in \{0,1\} \end{cases} \end{align}

For example, for the following matrix, I'd like to select the bolded elements:

\begin{equation} \left[ \begin{array}{cccc} \mathbf{4} & 2 & 1 & 2 \\ 0 & \mathbf{7} & 3 & 1 \\ 4 & 0 & 1 & \mathbf{9} \end{array} \right] \end{equation}

Until now, I have tried:

• brute force testing all possible combinations of $p$ elements to check if they satisfy the restrictions, which needs $\binom{mn}{p}$ tests
• not-so-brute test of all possible permutations of all $p-$combinations of the largest dimension $q = \max\{m,n\}$. This seems to need $q!\cdot p$ tests.

I have considered sorting all elements by value, and testing combinations in decreasing value order until one is found that satisfy the criteria, but haven't come up with an algorithm to accomplish that.

My searches for an existing algorithm have been unfruitful; any pointer is appreciated.

Put in $\max(m+n) - \min(m,n) = |m-n|$ fake rows (or columns) as needed to make a square. Put all the same value, all $0$ if allowed, in the fake entries. Then optimize for the square