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.

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

share|improve this question

2 Answers 2

up vote 1 down vote accepted

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

share|improve this answer
    
How do you prove that it actually gives us the minimum? –  Arnaud Jun 27 at 6:29
    
Edited to show more details. –  Wonder Jun 27 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?

share|improve this answer
    
Sorry, I have forgotten something.. (see edit) –  Arnaud Jun 27 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 at 4:45
    
Unfortunately it doesn't generalize easily... –  Arnaud Jun 27 at 4:46
    
If you were to think of sorting the lists.... –  Ross Millikan Jun 27 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 at 4:56

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.