0
$\begingroup$

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

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

1 Answer 1

-1
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ Could you elaborate your answer a bit? $\endgroup$
    – Evil
    Nov 13, 2017 at 19:58
  • $\begingroup$ Which part ? :) The reduction or the Branch and Bound ? $\endgroup$
    – Ricocotam
    Nov 13, 2017 at 23:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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