# 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?

• This is a mediant sum. Gerhard "Pick The M Biggest Ratios" Paseman, 2020.01.16. Jan 17 '20 at 0:58
• @GerhardPaseman: "Pick The M Biggest Ratios" doesn't always work. In the case N=3, M=2, and pairs (80,100), (20,100), and (1,20), it is best to pick the first and third pairs, even though the first and second pairs have the M biggest ratios. See my answer for a link to a good discussion.
– aorq
Jan 21 '20 at 15:08

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.

• Great reference, thanks! Jan 21 '20 at 20:04
• I had forgotten, but your answer reminded me: there's a linear time algorithm for the original question (motivated by the same context of dropping lowest grades) in D. Eppstein and D. S. Hirschberg, "Choosing subsets with maximum weighted average", J. Algorithms 24: 177–193, 1997, doi.org/10.1006/jagm.1996.0849, ics.uci.edu/~eppstein/pubs/EppHir-TR-95-12.pdf Jan 21 '20 at 21:22

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.