Optimization algorithm sought 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?
 A: 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.
A: 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.
A: 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)$.
