# Finding optimal subset for quadratic function

Given a set of $n$ elements $e_1,...e_n$ where each element $i$ is associated with two positive integers $\alpha_i$ and $\beta_i$. Given another integer $\lambda$, the goal is to find a set $S$ of elements such that $(\lambda - \sum_{e_i \in S}\alpha_i)^2 + \sum_{e_i \in S}\beta_i$ is minimize (for $\sum_{e_i \in S}\alpha_i < \lambda, a_i >0, b_i >0$). i'm looking for an exact or an approximate polynomial solution (my tries shows that a greedy solution (with respect to $\beta$ or the additional cost does not yield good approximation).

For all $\beta_i = 0$, asking whether one can get objective function value $1$ is equivalent to Subset Sum, and therefore NP-complete. Simple reductions from Subset Sum also prove that it is NP-complete to approximate the objective function within any factor polynomial in $n$.
We can reduce the $\beta_i = 0$ case to the case where $\beta_i = 1$ by just setting all $\beta_i$ values to $1$ and scaling both $\lambda$ and all $\alpha_i$'s by the same (large) integer factor. Then the $\beta_i$'s dont affect the objective function significantly anyway.
On the other hand, if all the integers $\alpha_i$ are small, one can solve the problem in pseudo-polynomial time - similar to the pseudo polynomial time algorithm for the Knapsack Problem. Thus for practical applications i'd expect that you can get good results by dividing down all the $\alpha_i$'s (and $\lambda$) by the same factor so that they become (relatively) small, round to the nearest integer, and solve using the Knapsack-like DP.
• Thanks you for your replay. I was missing the problem constraints. Find an optimal solution for $\sum_{e_i \in S}\alpha_i < \lambda, a_i >0, b_i >0$ (also fixed the original post). – liron Nov 5 '14 at 11:29