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$?

  • 2
    $\begingroup$ Have you tried any other approaches? Have you tried proving that the problem is hard? $\endgroup$ – Yuval Filmus Nov 13 '17 at 13:04
  • 2
    $\begingroup$ 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? $\endgroup$ – Yuval Filmus Nov 13 '17 at 13:11

Did you check what's the class of your problem? I'd try a reduction to a scheduling problem.

If you want to have something so you solve it today, use Branch and Bound. Bounds should be easy to find.

| cite | improve this answer | |
  • 1
    $\begingroup$ Could you elaborate your answer a bit? $\endgroup$ – Evil Nov 13 '17 at 19:58
  • $\begingroup$ Which part ? :) The reduction or the Branch and Bound ? $\endgroup$ – Ricocotam Nov 13 '17 at 23:42

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.