Return to Revisions

I have a very bad but polynomial time algorithm: 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$. For $i,j \in [n]\backslash S$ with $b_j>b_i$ we have $$c_{S\cup i}=\frac{a_S+a_i}{b_Sb_i}>\frac{a_S+a_j}{b_Sb_j}=c_{S\cup j} \Leftrightarrow a_S>\frac{a_jb_i-a_ib_j}{b_j-b_i}.$$ We compute the values $\frac{a_jb_i-a_ib_j}{b_j-b_i}$ for all pairs $(i,j)$. This values divide $\mathbb{R}$ into maximal $\binom{n}{2}+1$ many intervals. We loop through all this intervals and assume each time that $a_S$ lies in this interval. For each pair $(i,j)$ we get a rule as follows $i\in S\Rightarrow j\in S$ (or vice versa). Let $i\in [n]$ be such that the number of $j\in [n]$ such that $i \in S\Rightarrow j\in S$ is maximal. It follows that if $i\in S$ then $S=[n]$. By Induction we compute the optimal set from $[n]\backslash i$ and its value compare it with $c_{[n]}$.