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?
$\begingroup$
$\endgroup$
2
asked Jan 17, 2020 at 0:24
-
$\begingroup$ This is a mediant sum. Gerhard "Pick The M Biggest Ratios" Paseman, 2020.01.16. $\endgroup$– Gerhard PasemanCommented Jan 17, 2020 at 0:58
-
$\begingroup$ @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. $\endgroup$– aorqCommented Jan 21, 2020 at 15:08
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
2
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.
-
-
$\begingroup$ 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 $\endgroup$ Commented Jan 21, 2020 at 21:22
$\begingroup$
$\endgroup$
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)$.
answered Jan 17, 2020 at 2:22
$\begingroup$
$\endgroup$
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.
