How can I prove the optimality of the following greedy algorithm.

Assume that a matrix $$\mathbf{R}$$ of size $$N\times N$$ is given such that $$r_{i,j} \ge r_{i,j+1}$$ for any $$i$$ and $$j$$, where $$r_{i,j}$$ is the $$i$$th row and $$j$$th column element of $$\mathbf{R}$$.

I will solve the following problem: $$\begin{array}{cl} \displaystyle \max_{K_i, i=1,\ldots,N} & \displaystyle f(K_1,\ldots,K_N)=\sum_{i=1}^N \sum_{j=1}^{K_i}r_{i,j}\\ \text{subject to} & \displaystyle \sum_{i=1}^N K_i = L, \end{array}$$ where $$L$$ is not greater than $$N$$.

Literally speaking, the above problem is to select $$L$$ items out of $$N$$ items, allowing duplicate selection, where the score obtained by selecting an item decreases as the number of times selected increases.

My greedy algorithm is as follows:

Given r[i,j] for all i and j.

for i=1:N
K[i] = 1.
end

repeat
i_star = argmax r[i,K_i] over i.
K[i_star] = K[i_star] + 1.
until L = sum K[i] over all i


Obviously, the above greedy algorithm will give an optimal solution to the above problem. However, I want to prove the solution derived by the algorithm is optimal.

I am trying to prove it using mathematical induction, but my proof is not as rigid as I hope since I failed to prove the optimal substructure of the problem. The optimal substructure implies that an optimal solution when $$L=k + 1$$ contains an optimal solution when $$L=k$$.

How can I prove it mathematically rigorously?

• why are you calling that $f(R)$? First of all, I see no reason to introduce the notation. Second of all, it depends on the $K_i$'s and not just $R$... – mathworker21 Jul 6 at 10:45

Let $$i_1,\ldots,i_L$$ be the choices made by the greedy algorithm, and consider any other solution $$S$$, which we think of as a multiset of indices in $$[N]$$. Let $$i_1,\ldots,i_R$$ be the maximal prefix such that $$S$$ contains $$i_1,\ldots,i_R$$. Suppose that $$i_{R+1}$$ appears $$s$$ times in $$i_1,\ldots,i_R$$ (and so, in $$S$$). Consider the solution obtained from $$S$$ by removing one of the elements $$j$$ from $$S \setminus \{i_1,\ldots,i_R\}$$ and replacing it by $$i_{R+1}$$. Suppose that $$j$$ appears $$t$$ times in $$S$$, and $$t' \leq t-1$$ times in $$i_1,\ldots,i_R$$. Then by doing the switch, the total value changes by $$r_{i_{R+1},s+1} - r_{j,t} \geq r_{i_{R+1},s+1} - r_{j,t'+1} \geq 0,$$ where the first inequality follows from $$t'+1 \leq t$$ and the nonincreasing of rows of $$r$$, and the second inequality follows from the definition of the greedy choice.
• Thank you for the answer. May I ask the following case? If $i_{R+1}$ appears $l$ times in $\mathcal{S}$, the total value changes achieved by switching $j$ to $i_{R+1}$ is not $r_{i_{R+1},s+1}$ but $r_{i_{R+1},l+1}$, isn't it? – Danny_Kim Jul 9 at 7:26
• In your example, $s=l$. – Yuval Filmus Jul 9 at 7:35
• Assume that $\mathcal{S} = \{i_1,\ldots,i_R,a,a,b,a,a\ldots\}$ and $i_{R+1}=b$. Also, assume that $b$ appears $s$ times in $\{i_1,\ldots,i_R\}$ but $b$ appears $l=s+1$ times in $\mathcal{S}$. Then, if we switch $a$ by $b$, the value will change by not $r_{b,s+1}-r_{a,t}$ but $r_{b,s+2}-r_{a,t}$. Is my question wrong? – Danny_Kim Jul 9 at 8:03
• In your example, $i_1,\ldots,i_R$ is not the maximal prefix contained in $S$, since $S$ also contains $i_1,\ldots,i_R,i_{R+1}$. Don’t forget that $S$ is a multiset, not a sequence! – Yuval Filmus Jul 9 at 8:06