Find a permutation that minimizes the sum

2
votes

I have an array of elements [(A1, B1), ..., (An, Bn)] (all are positive floats and Bi <= 1) and I need to find such permutation which mimimizes the sum A1 + B1 * A2 + B1 * B2 * A3 + ... + B1 * ... B(n-1) * An.

Definitely I can just try all of them and select the one which gives the smallest sum (this will give correct result in O(n!)).

I tried to change the sum to A1 + B1 * (A2 + B2 * (A3 + B3 * (... + B(n-1) * An)) and tried to use a greedy algorithm which grabs the biggest Ai element on each of the steps (this does not yield a correct result).

Now when I look at the latest equation, it looks to me that here I see optimal substructure A(n - 1) + B(n - 1) * An and therefore I have to use dynamic programming, but I can not figure out correct direction. Any thoughts?

1
algorithmdata-structuresdynamic-programming
Without losing generally let’s assume An>=An-1 …. >= A2 >= A1 if Bi have same sequence, then answer is obviously A1 + B1 A2 + B1 B2 A3 + …. . In the case that everything is not that easy and Bi don’t have the same sequence like Ai, then I think there is not a way to find the best answer in polynomial time, maybe you could find the approximately the best answer in polynomial time with greedy or DP but you can’t find the exact smallest answer in polynomial time. – Lrrr
@AliAmiri no, if An > An-1 it does not mean that Bn > Bn-1, and I am mostly sure that there is a polynomial solution for this problem, because I have to do this for a pretty big amount of data. – Salvador Dali
currently I'm at work and also I dont remember NP-Problem mapping approach very good, but I think it could be proved that is NP, but I think there is lots of modification that you could do and reduce running time. But I hope I'm wrong and this is not NP :) – Lrrr

1 Answers

4
votes

I think this can be solved in O(N log(N)).

Any permutation can be obtained by swapping pairs of adjacent elements; this is why bubble sort works, for example. So let's take a look at the effect of swapping entries (A[i], B[i]) and (A[i+1], B[i+1]). We want to find out in which cases it's a good idea to make this swap. This has effect only on the ith and i+1th terms, all others stay the same. Also, both before and after the swap, both terms have a factor B[1]*B[2]*...*B[i-1], which we can call C for now. C is a positive number.

Before the swap, the two terms we're dealing with are C*A[i] + C*B[i]*A[i+1], and afterwards they are C*A[i+1] + C*B[i+1]*A[i]. This is an improvement if the difference between the two is positive:

C*(A[i] + B[i]*A[i+1] - A[i+1] - B[i+1]*A[i]) > 0

Since C is positive, we can ignore that factor and look just at the As and Bs. We get

A[i] - B[i+1]*A[i] > A[i+1] - B[i]*A[i+1]

or equivalently

(1 - B[i+1])*A[i] > (1 - B[i])*A[i+1]

Both of these expressions are nonnegative; if one of B[i] or B[i+1] is one, then the term containing 'one minus that variable' is zero (so we should swap if B[i] is one but not if B[i+1] is one); if both variables are one, then both terms are zero. Let's assume for now that neither is equal to one; then we can rewrite further to obtain

A[i]/(1 - B[i]) > A[i+1]/(1 - B[i+1])

So we should compute this expression D[i] := A[i]/(1 - B[i]) for both terms and swap them if the left one is greater than the right one. We can extend this to the case where one or both Bs are one by defining D[i] to be infinitely big in that case.

OK, let's recap - what have we found? If there is a pair i, i+1 where D[i] > D[i+1], we should swap those two entries. That means that the only case where we cannot improve the result by swapping, is when we have reordered the pairs so that the D[i] values are in increasing order -- that is, all the cases with B[i] = 1 come last (recall that that corresponds to D[i] being infinitely large) and otherwise in increasing order of D[i] value. We can achieve that by sorting with respect to the D[i] value. A quick examination of our steps above shows that the order of pairs with equal D[i] value does not impact the final value.

Computing all D[i] values can be done in a single, linear-time pass. Sorting can be done with an O(N log(N)) algorithm (we needed the swapping-of-neighbouring-elements stuff only as an argument/proof to show that this is the optimal solution, not as part of the implementation).