<p>For all $\beta_i = 0$, asking whether one can get objective function value $1$ is equivalent to <a href="http://en.wikipedia.org/wiki/Subset_sum_problem" rel="nofollow">Subset Sum</a>, 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$.</p>

<p>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. </p>

<p>On the other hand, if all the integers $\alpha_i$ are small, one can solve the problem in pseudo-polynomial time - similar to the <a href="http://en.wikipedia.org/wiki/Knapsack_problem#Dynamic_programming" rel="nofollow">pseudo polynomial time algorithm for the Knapsack Problem</a>. 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.</p>

CC BY-SA 3.0
2014-11-05T11:29:21.800Z
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
CC BY-SA 3.0
2014-11-05T23:37:18.157Z
I edited the answer to incorporate your constraints - this does not really change anything (except that the proof for hardness of approximation becomes a tad more non-trivial)
daniello
CC BY-SA 3.0
2014-11-04T23:46:19.343Z
2014-11-05T23:36:22.927Z
2014-11-05T23:36:22.927Z
daniello
<p>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 &lt; \lambda, a_i &gt;0, b_i &gt;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).</p>

<ds.algorithms><optimization><approximation>
Finding optimal subset for quadratic function
liron
# Finding optimal subset for quadratic function

(Asked by: username_0 on 2014-11-04)

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).

**Tags:** ds.algorithms, optimization, approximation

---

## 1 answers

### Answer by username_1 on 2014-11-04. Score: 5

For all $\beta\_i = 0$, asking whether one can get objective function value $1$ is equivalent to [Subset Sum](http://en.wikipedia.org/wiki/Subset_sum_problem), 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](http://en.wikipedia.org/wiki/Knapsack_problem#Dynamic_programming). 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.

> **Comments:**
> **username_0**: 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).  
> **username_1**: I edited the answer to incorporate your constraints - this does not really change anything (except that the proof for hardness of approximation becomes a tad more non-trivial)  

---

