Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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

2 Answers 2

up vote 1 down vote accepted

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

share|improve this answer
    
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.

share|improve this answer
    
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
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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