# Minimizing the SUM algorithm

We are given $2n$ positive integers $a_1,a_2\ldots,a_n$ and and $$b_1,b_2,\ldots,b_n$$ as input.

The question is to find a permutation $O$ on $\{1,2,\ldots,n\}$ that minimizes $$\sum_{i=1}^n \left(a_{O(i)} \cdot \sum_{j=1}^i b_{O(j)}\right).$$

For example, take $n = 3$, $a_1 = 10, a_2 = 1, a_3 = 100, b_1 = 10, b_2 = 100$, and $b_3 = 1$. If we take $O$ so that $O(1) = 1, O(2) = 3$, and $O(3) = 2$, we have $$\sum_{i=1}^n \left(a_{O(i)} \cdot \sum_{j=1}^i b_{O(j)}\right) = 1311.$$

The desired output is $O(1) = 3, O(2) = 1$, and $O(3) = 2$, which yields $$\sum_{i=1}^n \left(a_{O(i)} \cdot \sum_{j=1}^i b_{O(j)}\right) = 321.$$

Trying all possibility is exponential. How can I find an optimal permutation $O$?

• Have you tried any other approaches? Have you tried proving that the problem is hard? – Yuval Filmus Nov 13 '17 at 13:04
• Given a solution $O$, consider what happens when you switch $O(i)$ and $O(j)$. When is this beneficial? What features does a local optimum satisfy? Can you extract an algorithm out of this? – Yuval Filmus Nov 13 '17 at 13:11