We are given 2ドルn$ 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– Yuval Filmus2017年11月13日 13:04:58 +00:00Commented 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$Yuval Filmus– Yuval Filmus2017年11月13日 13:11:47 +00:00Commented Nov 13, 2017 at 13:11
1 Answer 1
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.
-
1$\begingroup$ Could you elaborate your answer a bit? $\endgroup$Evil– Evil2017年11月13日 19:58:11 +00:00Commented Nov 13, 2017 at 19:58
-
$\begingroup$ Which part ? :) The reduction or the Branch and Bound ? $\endgroup$Ricocotam– Ricocotam2017年11月13日 23:42:45 +00:00Commented Nov 13, 2017 at 23:42