2
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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

As a tip for how you could discover this on your own: play with some examples. If you try many examples and work out by hand the optimal solution, you might happen to notice the pattern (that the best ratio for the sums matches the largest ratio of columns), and that would give you a hypothesis that you could then try to prove.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – G. Bach Jan 16 '16 at 11:46
  • $\begingroup$ @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? $\endgroup$ – drzbir Jan 16 '16 at 17:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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