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.
Thank you all for the comments and answers. After posting this question, I thought it for a while. It may be NP-complete. Please see the outline of my proof.
Partition: given positive integers $\{a_1,\ldots,a_n\}$, find a subset $S$ such that $$ \sum_{i\in S} a_i = 1/2 \cdot \sum_{i=1}^n a_i. $$
Let $\sum_{i=1}^n a_i =2K$. We set $b_i$ as follows: $b_i=e^{a_i/K}$ for each $i$. Then, for each subset $S$, $$ \frac{\sum_{i\in S} a_i}{\Pi_{i\in S} b_i}= \sum_{i\in S} a_i \cdot e^{-\sum_{i\in S} a_i/K} $$ Let function $H(x)=x e^{-x/K}$, where $x=\sum_{i\in S} a_i$. It is straightforward to verify that $H(x)$ is increasing in $x$ for $x\leq K$; it is decreasing in $x$ for $x\geq K$. Therefore, it has the unique maximum at $x=K$, i.e., $H(x)\leq H(K)=K/e$. Then, $$ \frac{\sum_{i\in S} a_i}{\Pi_{i\in S} b_i}= \sum_{i\in S} a_i \cdot e^{-\sum_{i\in S} a_i/K} \leq \max_x H(x)=K/e. $$ Thus, the original problem maximized if and only if there exists a subset $S$ such that $\sum_{i\in S} a_i =K$, which is the solution to the Partition problem.
Edit: Original proof was wrong and I couldn't fix it. The algorithm does not work in general.
For $S\subset [n]$ let $a_S=\sum_{i\in S} a_i$, $b_S=\prod_{i\in S} b_i$ and $c_S=a_S/b_S$. If $S$ is optimal, $i \in S$ and $j\in [n]\backslash S$ we have $$\frac{a_S}{b_S}=c_{S}\geq c_{(S\backslash i)\cup j}=\frac{a_S-a_i+a_j}{b_Sb_j/b_i}$$ Hence $a_S(b_j-b_i)\geq b_i(a_j-a_i)$ and therefore $$\begin{cases} a_S\geq \frac{(a_j-a_i)b_i}{b_j-b_i} & \text{if } b_i>b_j\\ a_S\leq\frac{(a_j-a_i)b_i}{b_j-b_i} & \text{if } b_i<b_j\\ a_j\leq a_i & \text{if }b_i=b_j\end{cases}.$$ The values $\frac{(a_j-a_i)b_i}{b_j-b_i}$ for all pairs $(i,j)\in [n]^2$ divide $\mathbb{R}$ into maximal $2\binom{n}{2}+1$ many intervals. We loop through all these intervals and assume each time that $a_S$ lies in the corresponding interval. If an inequality above is violated we get that $i\in S \Rightarrow j \in S$. We consider a directed graphs with vertex set $[n]/\sim$ with $i\sim j$ iff $(a_i,b_i)=(a_j,b_j)$ and a edge from $i$ to $j$ iff $i\in S \Rightarrow j \in S$. Originally I presented a wrong proof where the graph had an edge between any two vertices and one could continue with that.
