# Maximize ratio of sums

I have a $2 \times n$ matrix of positive integers, where the elements are denoted by $a_{ij}$ for all $i$ in the set $\{1,2\}$ and for all $j$ in the set $\{1,\ldots,n\}$.

I would like to select a subset $S$ of the columns that maximizes the ratio $$\left(\sum_{j\in S}a_{1j}\right) / \left(\sum_{j\in S}a_{2j}\right)\,.$$

Can this be done efficiently? Is this a known problem?

For example, if

$$A=\begin{pmatrix} 1 & 2 \\ 2 & 3\end{pmatrix},$$

then the best thing to do is to choose the second column. Because, (i) if I choose column $1$ I will get $1$ as the sum of the first row and $2$ as the sum of the second row, (ii) if I choose column $2$ I will get $2$ as the sum of the first row and $3$ as the sum of the second row and (iii) if I choose column $1$ and column $2$ I will get $3$ as the sum of the first row and $5$ as the sum of the second row.

There's a linear-time algorithm for this problem. Find the index $j$ that maximizes the ratio $r_j = a_{1j} / a_{2j}$. This $r_j$ is the maximum possible value of the ratio of sums.
Proof: The ratio of sums can be made $\ge c$ if and only if there exists a set $S$ such that $\sum_{j \in S} a_{1j} - c a_{2j} \ge 0$. That's possible iff there exists $j$ such that $a_{1j} - c a_{2j} \ge 0$, i.e., such that $a_{1j}/a_{2j} \ge c$.
• Maybe to add this. $\frac{a}{b} \geq \frac{a+c}{b+d} \iff ab + ad \geq ab + bc \iff ad \geq bc \iff \frac{a}{b} \geq \frac{c}{d}$ where all equivalences use that we only have positive numbers. – G. Bach Jan 16 '16 at 11:46
• @D.W. Thank you very much for your help. I tried to modify the problem a little bit. Instead of maximizing the ratio of the sums $\frac{\sum_i a_{1i}}{\sum_i a_{2i}}$, let's maximize the ratio of the modified sums $\frac{1+\sum_i a_{1i}}{\sum_i a_{2i}}$. I tried the same steps as your proof, I ended up with iff $\sum_i ca_{1i} -a_{2i}\geq -c$. But I think I cannot go further as you did, right? – drzbir Jan 16 '16 at 17:11