The maximum ratio of the minimum subset and the maximum subset of size k in a set of n pairs of values
So, let's say you have a set of value pairs in the form {x, y}, such as {1, 2}, {1, 3}, and {2, 5}. Then you need to find a subset of k pairs (in this case, say k = 2) so that the ratio of the sum of all x in the subset divided by all y in the subset is as high as possible.
Could you please point me in the direction for the relevant theory or algorithms? It's kind of like the maximum sum of a subset, but since the pairs are "related" to each other, it introduces a constraint that changes it to problems I know of.
source to share
I originally thought a simple greedy approach might work here, but commenters have noted some examples of counter examples.
Instead, I think the bisection approach should work.
Suppose we want to know if the ratio g can be achieved.
We need to add a selection of k vectors to be above the gradient line g.
If we project each vector perpendicular to this line to get p1, p2, p3 values, then the final vector will be above the line if and only if the sum of the p values is positive.
Now, with the predicted values, it seems correct that the optimal solution is to choose the largest k.
We can then use halving to find the highest possible ratio.
Mathematical justification
Suppose we want to relate above g, i.e.
(x1+x2+x3)/(y1+y2+y3) >= g
=> (x1+x2+x3) >= g(y1+y2+y3)
=> (x1-g.y1) + (x2-g.y2) + (x3-g.y3) >= 0
=> p1 + p2 + p3 >= 0
where pi is defined as xi-g.yi.
source to share