1
$\begingroup$

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?

  • 0
    @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.2011-08-04

2 Answers 2

1

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

  • 0
    I've tested this approach for `N` up to 20 (to check the result by bruteforce), it works fine. Thanks!2011-08-04
0

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.

  • 0
    @Peter, you're absolutely right. I didn't catch that that was what OP meant by "parallel arrays". Edit in progress.2011-08-04