Maximize the sum ratio

Let S be K positive sequences Ai, Bi of length N. We want to maximize the Ratio of the sum of each of AB

${\mathrm{argmax}}_S\frac{{\sum }_{i\in S}{B}_i}{{\sum }_{i\in S}{A}_i}$

Instead of directly maximizing the ratio of sums, there is a solution method that makes it a problem of determining whether the ratio of sums is greater than or equal to X, and then bisectively searching for X

• $\frac{\sum B_i}{\sum A_i}\ge X$
• $\sum B_i\ge X\sum A_i$
• $\sum B_i-X\sum A_i\ge 0$
• $\sum (B_i-X{A}_i)\ge 0$ If there exists an S satisfying the condition, then the K selections from which $B_i-X{A}_i$ is larger satisfy the condition. Therefore, this decision problem can be solved by O(NlogN).

A dichotomous search of this X will find the largest X for which S satisfies the condition. This is the maximum value of X.

• Maximize concentration

---

This page is auto-translated from /nishio/和の比率の最大化 using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I’m very happy to spread my thought to non-Japanese readers.