0
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – liron Nov 5 '14 at 11:29
  • $\begingroup$ 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) $\endgroup$ – daniello Nov 5 '14 at 23:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.