Let $I, J, n \in \mathbb N$. Furthermore, let $\mathbf M \in \mathbb N^{I \times J}$. Finally, for $i \in \{1, \dots, I\}$ and $j \in \{1, \dots, J\}$, let $M(i,j)$ denote the element in the $i$th row and $j$th column of $\mathbf M$. I'd like to solve the following optimization problem:
\begin{equation} \begin{aligned} &\max_{\mathbf x \in \mathbb N^I} && \sum_{i=1}^I\sum_{j = 1}^J\min\{M(i,j), x_i\} \\ &\text{ s.t.} && \sum_{i=1}^I x_i = n. \end{aligned} \end{equation}
I suspect that the problem can be solved by a "greedy" algorithm with the following form:
- Set $\mathbf x \equiv \mathbf 0$.
- Pick any $\mathbf k \in \arg \max \sum_{i=1}^I\sum_{j = 1}^J\min\{M(i,j), x_i + \delta_k\}$. In words, find a component of $\mathbf x$ which maximally increases the objective value when incremented by one -- allowing for the possibility that there may be multiple components which give maximal increase.
- Set $\mathbf x \equiv \mathbf x + \mathbf e_k$, where $\mathbf e_k$ is the $k$th coordinate vector.
- If $\sum_{i=1}^I x_i = n$, stop; otherwise, return to step 2.
However, I am not sure how to prove that this greedy algorithm leads to an optimal solution.
Can you help me by either providing a proof or counter-example?