Suppose I have $N$ pairs of positive numbers $(a_1, b_1), (a_2, b_2), \dotsc, (a_N, b_N).$ and I want to find a subset of $M$ of them maximizing $$ \frac{\sum_{j=1}^M a_{i_j}}{\sum_{j=1}^M b_{i_j}}. $$
Can this be done in polynomial time?
MathOverflow is a question and answer site for professional mathematicians. It only takes a minute to sign up.
Sign up to join this communitySuppose I have $N$ pairs of positive numbers $(a_1, b_1), (a_2, b_2), \dotsc, (a_N, b_N).$ and I want to find a subset of $M$ of them maximizing $$ \frac{\sum_{j=1}^M a_{i_j}}{\sum_{j=1}^M b_{i_j}}. $$
Can this be done in polynomial time?
The paper "Dropping Lowest Grades" by Daniel M. Kane and Jonathan M. Kane addresses this question in the context of dropping $r$ quiz grades from a collection of weighted grades.
The solution described there is fundamental the same as that in David Eppstein's answer. However, there is also a discussion of a practical implementation that may be even faster in practice.
It is equivalent to look for the largest positive value $x$ such that, for some $M$-subset, $\sum (a_i-x b_i)\ge 0$.
Plot the $n$ lines $y = a_i - x b_i$ in the plane. The $M$-subset that maximizes $\sum (a_i-x b_i)$ for a given $x$ is the one defined by the $M$ lines from this arrangement that have the highest crossings with a vertical line through $x$. (If you trace out, for each $y$, the $M$th-from-top line in this arrangement, the trace is a polygonal curve describing the optimal subset for each $x$.) You can use a binary search among the crossings of the arrangement to find the largest $x$ whose optimal subset is good enough.
This immediately gives you $O(n^2)$ time but by using techniques from https://en.wikipedia.org/wiki/Theil%E2%80%93Sen_estimator to find medians of sets of crossings more quickly you can reduce it to $O(n\log^2 n)$.
I don't know about polynomial time, but here's an integer linear programming formulation. For $i\in\{1,\dots,N\}$, let binary decision variable $x_i$ indicate whether pair $(a_i,b_i)$ is selected. The problem is to maximize $$\frac{\sum_{i=1}^N a_i x_i}{\sum_{i=1}^N b_i x_i}$$ subject to $$\sum_{i=1}^N x_i = M.$$
Now linearize the objective via the Charnes-Cooper transformation, as discussed here.