Element wise product sum of two arrays

Question

I have two arrays, namely $a$ and $b$. Both have the same length $n$. I have to find the maximum value of $\sum a_i b_j$, in which every element can be used at most one time. My algorithm for solving this problem is:

1. Sort both $a$ and $b$ in non increasing order.
2. Pick the values from the array in order of greatest to smallest. Calculate their product and add them to sum.

On the arrays $a = \{2,3,4\}$ and $b = \{4,5,6\}$, the algorithm runs as follows:

• Firstly, sorting the arrays: $a = \{4,3,2\}$ and $b = \{6,5,4\}$.

Then picking values from the first to last, gives the answer $(4\cdot6) + (3\cdot5) + (2\cdot4) = 24 + 15 + 8 = 47$.

Here what I have used is a greedy algorithm. How to prove its correctness? What I want to know is, how to prove that this algorithm always gives the maximum answer?

Answer 1

The usual formulation of this problem is: find a permutation $\pi$ that maximizes $\sum_i a_i b_{\pi(i)}$.

Towards solving this problem, suppose that we have some permutation $\pi$ in mind, and let $\sigma$ result from switching $\pi(j)$ and $\pi(k)$ (that is, $\sigma(k) = \pi(j)$ and $\sigma(j) = \pi(k)$. When is this beneficial? $$ \sum_i a_i b_{\sigma(i)} - \sum_i a_i b_{\pi(i)} = a_j (b_{\sigma(j)} - b_{\pi(j)}) + a_k (b_{\sigma(k)} - b_{\pi(k)}) = (a_j-a_k)(b_{\pi(k)}-b_{\pi(j)}). $$ That is, if $a_j > a_k$ and $b_k < b_j$ then it is beneficial to switch $\pi(j)$ and $\pi(k)$. Conversely, any local maximum must satisfy the constraint that if $a_j > a_k$ then $b_{\pi(j)} \geq b_{\pi(k)}$.

Using this property you can prove that your algorithm is optimal. I'll let you fill in the remaining details.

Answer 2

Generally, to prove a greedy algorithm is optimal what you do is come up with a theorem that captures the idea of “moving away from” the greedy strategy and show that that decreases the optimal value. It’s important that you phrase the theorem in a way that can be iteratively applied, as otherwise it might be that the objective function goes down immediately after departing from the greedy algorithm, and then goes back up. In this case, you want

Theorem: If $a\geq b$ and $c\geq d$ then $ac+ bd\geq ad+bc$

Given any way of pairing numbers, this theorem says that if you swap two numbers so that you move closer to the greedy algorithm then the value cannot go down, and if you swap two numbers so that you move further from the greedy algorithm the value cannot go up. So prove this, and the correctness of the greedy algorithm follows.

It’s sufficient to consider only vectors of length two because any permutation of the vectors can be generated from exchanging two numbers. Equivalently, $S_n$ is generated by its two-cycles for every $n>1$