Skip to main content
3 of 3
Improved title, fixed typos and made the problem statement cleaner.
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

Complexity of finding the maximum sum divided by product

What is the complexity of the following optimization problem?

Problem. Given $n$ pairs of positive reals $(a_i,b_i)_{i=1}^n$, choose a subset $S \subseteq [n]$ to maximize $$ \frac{\sum_{i\in S} a_i}{\Pi_{i\in S} b_i}. $$ How do we efficiently solve it? Or is it NP-hard? Thanks a lot.