# Minimize Sum a_i / Sum b_i over subsets

I have two positive finite sequences $a_i$ and $b_i$, with $0 \leqslant i \leqslant n$. The problem is to find the subset $I$ of $\{0, ..., n\}$ that minimizes:

$$\frac{\sum_{i \in I} a_i}{\sum_{i \in I} b_i}$$

in an efficient way from the algorithmic point of view. Have you any ideas please?

[EDIT] SORRY: the cardinal of $I$ is a given value in the problem... let's call it $m$.

-

$O(n^2)$ is not too hard, here is an inductive approach.

Induction is on n, keeping m constant.

Base case: if n = m, then pick all i for I.

Inductive case:

Suppose I have the best subset S till n-1. Either S is still the best for n, or I have to replace one of the elements in S by n. I can evaluate all these options in O(n) time by pre-computing sums of as and bs for S.

$T(n) = T(n-1) + O(n)$ gives $T(n) = O(n^2)$

EDIT: To prove correctness, most cases are already explicitly dealt with. We just have to exclude the possibility that the best set containing n is not one of the candidates we have obtained here.

Suppose the sum of a's from the (n-1) case is a, and the sum of the b's there be b.

Suppose the sums obtained by this process after the inductive step are (a+p, b+q).

Suppose there exist some bad set like this. Suppose the numerator of the actual least ratio here is (a+p+s) and the denominator is (b+q+r).

We want to prove that if $\frac{a}{b} \lt \frac{a+s}{b+t}$ then $\frac{a+p}{b+q} \lt \frac{a+p+s}{b+q+t}$

The first condition is equivalent to $\frac{a}{b} \lt \frac{s}{t}$ while the second one is equivalent to $\frac{a+p}{b+q} \lt \frac{s}{t}$. However, $\frac{a+p}{b+q} \lt \frac{a}{b}$ by construction so if the first condition holds then second one does too.

The reason why simple sorting does not work is because the conditions on the ratios are on the values s, t, p, q which are of the form (sum of elements in A-B) - (sum of elements in B-A), not on the a's and b's themselves. This approach takes care of that.

-
How do you prove that it actually gives us the minimum? – Arnaud Jun 27 '14 at 6:29
Edited to show more details. – Wonder Jun 27 '14 at 7:28

Hint: suppose you have some subset $I$ with a ratio $\frac ab$ and add one more element to make a subset $I'$. Does the ratio increase or decrease?

-
Sorry, I have forgotten something.. (see edit) – Arnaud Jun 27 '14 at 4:41
The answers you have should give a good idea for the answer, then. We answered for $m=1$ Now that you have that, what is your idea for $m=2?$ – Ross Millikan Jun 27 '14 at 4:45
Unfortunately it doesn't generalize easily... – Arnaud Jun 27 '14 at 4:46
If you were to think of sorting the lists.... – Ross Millikan Jun 27 '14 at 4:48
Counter-example: 1/10, 1/10, 1/10, 1/10, 1.5/10, 140/1000, and you have to remove one element. It is better to remove the last one. – Arnaud Jun 27 '14 at 4:56