I want to find an approximation algorithm for the following problem.
$\qquad$ Find a $S\subseteq N$ such that $\rho(S) = \frac{\sum_{i\in S}\ V_i}{(1+\sum_{i\in S}\ V_i)(4+\sum_{i\in S}\ V_i)}$ is maximized. (All $V_i$s are positive and known.)
Is there any heuristic $\hat S\subseteq N$ such that $\rho(\hat S) \ge \alpha \max_{S\subseteq N}\rho(S) $ for some constant $\alpha$?
Denote $V(S) = \sum_{i\in S} V_i$. Introduce two problems as follows:
Problem 1 (subset sum)
$$S_L^* := Argmax_{S} V(S), \ \ s.t. \ \ V(S)\le 2$$
Problem 2 (reference)
$$S_R^*: = Argmin_{S} V(S), \ \ s.t. \ \ V(S)\ge 2$$
Clearly $\max_S \rho(S) = \max\{\rho(S_L^*),\rho(S_R^*)\}$ as $\rho(S)$ is strictly quasi-concave in $V(S)$ and attains its maximum at $V(S)=2$. For problem 1, we can find a set $S_L$ in polynomial time such that $V(S_L) \in [V(S_L^*)/2, V(S_L^*)]$. For problem 2, we can find a set $S_R$ in polynomial time such that $V(S_R) \in [V(S_R^*), 2V(S_R^*)]$.
As $\rho(S_L) \ge \rho(S_L^*)/2$ and $\rho(S_R) \ge \rho(S_R^*)/2$, we have $$\max \{\rho(S_L),\rho(S_R)\}\ge \max_S \rho(S)/2.$$