# Valued permutation

Here is original problem.

Problem: there are 2 parallel arrays of positive floating point numbers A (Ai < 1000) and B (Bi < 1) of size n.

How to find the minimal value for the following target function:

F(A, B) = Ak + Bk * F(A', B')

where A', B' denote the arrays A and B with their k:th element removed.

How to apply on such kind of problems, where we need to evaluate given function on a permutation?

Answers came up with some kind of heuristics, however we need optimal polynomial solution. Anyone can suggest the approach for this?

-
Presumably, this is a recursive definition, but then don't you have to give a base case, e.g., $F(A,B)$ when $A$ and $B$ are empty? Also, it would seem that the right side depends on $k$ and the left side doesn't, which is very troubling. And, then, I don't understand what you mean by "the minimal value". Do you mean, minimal over all possible choices of $A$ and $B$? Question is hugely unclear. – Gerry Myerson Aug 4 '11 at 7:20
@Gerry, I think it's pretty clear that he's after a strategy for picking the $k$ at each level of the recursion. That would also explain the title "Valued permutation". – Peter Taylor Aug 4 '11 at 7:25
@Gerry, F({}, {}) = 0. So, after picking up all terms, we came with some permutation of the items in the parallel arrays. So our goal is to evaluate minimal value for this target function. – Anton Postnikov Aug 4 '11 at 7:36

I would calculate $\frac{B_k-1}{A_k}$ and do those with smaller (including more negative) results on the most outside position of the recursion.

This is at locally optimal in that you cannot swap a pair of adjacent choices and improve, and therefore globally optimal, since the algorithm gives a unique solution apart from equal values of $\frac{B_k-1}{A_k}$, which make no difference. Any other solution which does not have this property is not optimal.

If we compare $A_1+B_1\times (A_2+B_2\times F)$ with $A_2+B_2\times (A_1+B_1\times F)$ then the former will be smaller (or the same) iff

$$A_1+B_1(A_2+B_2 F) \le A_2+B_2(A_1+B_1 F)$$

$$A_1+ B_1 A_2+B_1 B_2 F \le A_2+B_2 A_1+B_2 B_1 F$$

$$B_1 A_2 - A_2 \le B_2 A_1 - A_1$$

$$\frac{B_1-1}{A_1} \le \frac{B_2-1}{A_2}$$

noting $A_k >0$.

The value of the empty $F(,)$ does not matter, as it appears in the end multiplied by all the $B_k$.

-
I've tested this approach for N up to 20 (to check the result by bruteforce), it works fine. Thanks! – Anton Postnikov Aug 4 '11 at 10:46

2ND EDIT: It appears that what's below was based on a misunderstanding of the problem. I thought one could permute the $A_i$ and the $B_i$ independently, whereas in fact it seems they are meant to be linked. That being the case, I suspect there is no algorithm significantly more efficient than just testing every permutation, which is to say, there is no efficient algorithm. But that's just a guess, I'm nowhere near being able to give a proof.

So it looks like you wind up with $$A_1+A_2B_1+A_3B_1B_2+\cdots$$ The sequence $B_1,B_1B_2,B_1B_2B_3,\dots$ is decreasing, so I think you want it to decrease as slowly as possible, so take $B_1\ge B_2\ge B_3\cdots$. Then to make the most of the $A_i$, take $A_1\ge A_2\ge A_3\cdots$.

Note that my subscripts are in reverse order; my $A_1$ is the last item chosen.

EDIT: the procedure above maximizes, the problem was to minimize, so, back to the drawing board. Also, I acted as though the base case was 1, when it's actually zero. And not only that, I thought I was reversing the order of the $A_i$, but I wasn't. So, here's what you do:

First, permute so $B_n$ is the largest of the $B_i$, because it's going to get multiplied by zero. Permute the other $B_i$ so that $B_1\le B_2\le\dots\le B_{n-1}$; that will minimize all the products of the $B_i$. Then, you want the biggest $A_i$ multiplying the smallest of the $B$-products, the smallest $A_i$ multiplying the biggest of the $B$-products, so permute the $A_i$ so that $A_1\le A_2\le A_3\le\dots\le A_n$.

See the example worked out in the comments.

-
I don't think this works, for example with $A=(3,2,4)$ and $B=(0.2,0.3,0.4)$ your solution gives $3+0.2\times(2+0.3\times(4+0.4\times 0))= 3.64$ while the optimal solution gives $2+0.3\times(3+0.2\times(4+0.4\times 0))= 3.14$. – Henry Aug 4 '11 at 10:20
@Henry, I see the problem: I forgot the goal was to minimize and wrote a procedure to maximize. The optimal solution for your example should be $2+.2(3+.3(4+(.4)(0)))=2.84$. I'll edit my answer. – Gerry Myerson Aug 4 '11 at 12:47
You appear to be ordering the $B_i$ and $A_i$ independently, but they share a subscript so their orders aren't independent. – Peter Taylor Aug 4 '11 at 13:01
@Peter, you're absolutely right. I didn't catch that that was what OP meant by "parallel arrays". Edit in progress. – Gerry Myerson Aug 4 '11 at 22:33