# Prove that a proposed algorithm gives an optimal solution of the optimization problem.

We have $N$ queues. Each of the queues contains a number of numbered ball, and the balls can be taken out in descending order. For example, the queues can be as the follows: I want to take $L$ balls from the queues such that the sum of the balls' numbers is as large as possible.

• Let us denote $i$th ball in the queue $q$ by $x_i^q$, e.g., $x_1^2=70$, $x_2^M=1600$.
• Let us denote the number of balls taken from the queue $q$ by $L_q$.

Then, the optimization problem is formulated as $$\text{maximize}\quad\sum_{q=1}^M\sum_{i=1}^{L_q} x_i^q,\qquad\text{subject to}\quad\sum_{q=1}^M L_q = L,$$ where the decision variables are $L_1, L_2, \ldots, L_q$.

I made a greedy algorithm.

First, set $L_q=0$ for all $q$. Then, select a queue $k$ whose first ball has the largest number. Then, take out a ball from the queue $k$ with updating $L_k$ to $L_k+1$. We repeat these procedures until $L$ balls are taken out from the queues. Finally, $L_1$, $L_2$, $\ldots$, $L_M$ are the solution.

The above algorithm is intuitively supposed to give an optimal solution, but I could've not yet mathematically proved that the output of the algorithm is optimal. Is there any way to prove the above algorithm gives the optimal solution? I am not only an rigorous proof but also very welcome advice on the direction for the proof.

• Suppose queue 1 has 5,10, queue 2 has 1, 1000 and L=2. If I understand your algorithm correctly, it chooses 5,10 instead of 1,1000. – saulspatz Mar 21 '18 at 16:39
• @saulspatz Supposing that a queue 1 has two balls with number 5 and 10, and a queue 2 has also two balls with number 1 and 1000. If we have to take out only two balls, then the optimal solution will be $L_1=1$ and $L_2=1$. Then, the objective value becomes $10+1000=1010$. (Algorithm also gives $L_1=L_2=1$.) – Danny_Kim Mar 21 '18 at 16:43
• Okay, I had it backwards. Your algorithm is simply to always take the largest available ball, and it clearly works. – saulspatz Mar 21 '18 at 16:56
• @saulspatz Yeah, I just wanna prove its optimality rigorously and mathematically. – Danny_Kim Mar 21 '18 at 16:57
• I still don't understand how your algorithm doesn't output $L_1=2$ and $L_2=0$ in @saulspatz 's example. – Rchn Mar 21 '18 at 17:18

## 1 Answer

The algorithm is to always choose the largest available number. Prove it by contradiction. Suppose the largest available number is $N,$ and consider any solution $S$ in which $N$ is not chosen. Replace the smallest $s \in S$ by $N$ to get a new solution $S'$. Now $N\ge s$ because $s$ is less than the element $x$ at the head of its queue, and $N\ge x$ so that $\sum S'>= \sum S.$ Either all the elements in $S'$ are equal to $N$ or we have a contradiction. In either, case, we see that an optimal solution must contain $N$.