Choose a subset $S$ from $(a_i,b_i)_{i=1}^n$ to maximize $$ \frac{\sum_{i\in S} a_i}{\Pi_{i\in S} b_i}. $$ Hot to efficiently solve it? Is it NP-hard? Here, each $a_i$ and $b_i$ are given, strictly positive. We want to find the best $S$. Thanks a lot.

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.

Choose a subset $S$ from $(a_i,b_i)_{i=1}^n$ to maximize $$ \frac{\sum_{i\in S} a_i}{\Pi_{i\in S} b_i}. $$ Hot to efficiently solve it? Is it NP-hard?

Choose a subset $S$ from $(a_i,b_i)_{i=1}^n$ to maximize $$ \frac{\sum_{i\in S} a_i}{\Pi_{i\in S} b_i}. $$ Hot to efficiently solve it? Is it NP-hard? Here, each $a_i$ and $b_i$ are given, strictly positive. We want to find the best $S$. Thanks a lot.