1

Suppose we are given pairs $(a_i,b_i)$ of positive numbers and $x \geq 1$. The goal is find the optimal subset of indices $I$ that maximizes:

$$\frac{(\sum_{i \in I} a_i)^x}{\sum_{i \in I} b_i}$$

This is a combinatorial optimization so I'm hoping to find an algorithm that runs really fast, e.g. $O(n)$ or $O(n \log n)$ time for $n$ pairs.

user2566092
  • 26,142
  • Is there a condition that $I$ must be of a certain size? – Brian Tung Apr 15 '15 at 15:19
  • @BrianTung No the subset can be anything, and my experiments that just use brute-force show that the optimal solution could be anything, as small as one pair or as large as all pairs. – user2566092 Apr 15 '15 at 15:21
  • It still seems as though you could try them in order of decreasing $a_i/b_i$. Does that work? It's $O(n \log n)$ to sort them, $O(n)$ to try out the successively lower ratios. – Brian Tung Apr 15 '15 at 15:23
  • Actually, let me think about this a bit. It might not be that simple. – Brian Tung Apr 15 '15 at 15:58
  • By examining optimal solutions in my suite of test problems, it does seem that the optimal solution consists of the top $k$ pairs for some $k$ where the pairs are ordered decreasing according to $a_i / b_i$. – user2566092 Apr 15 '15 at 16:03

0 Answers0