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.

    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?

  • $\begingroup$ 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$... $\endgroup$ – 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.

  • $\begingroup$ 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? $\endgroup$ – Danny_Kim Jul 9 at 7:26
  • $\begingroup$ In your example, $s=l$. $\endgroup$ – Yuval Filmus Jul 9 at 7:35
  • $\begingroup$ 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? $\endgroup$ – Danny_Kim Jul 9 at 8:03
  • $\begingroup$ 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! $\endgroup$ – Yuval Filmus Jul 9 at 8:06
  • $\begingroup$ Oh my god, I finally understood thanks to your one more mention of MULTISET. Thank you very much. $\endgroup$ – Danny_Kim Jul 9 at 8:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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