0
$\begingroup$

Given a set $𝑁=\{π‘Ž_1,β‹―,π‘Ž_𝑛\}$ where all $π‘Ž_𝑖$s are rational positive numbers and $\sum_{i\in N}a_i=1$, find a subset π‘†βŠ†π‘ such that $(\sqrt{2\sum_{i\in S}a_i}-1)^2$ is minimized. Does the appearance of √ make the problem ill-defined with regrading to complexity?

$\endgroup$
3
$\begingroup$

The appearance of square roots does not make this an ill-defined problem.

Note that $(\sqrt{2\sum_{i\in S}a_i}-1)^2=0$ if $\sum_{i\in S}a_i = 1/2$ and $(\sqrt{2\sum_{i\in S}a_i}-1)^2>0$ otherwise. Therefore, the problem is easily seen to be NP-hard by reduction from subset sum.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you, Prof. Zanden. $\endgroup$ – GPI Feb 26 at 16:53
-1
$\begingroup$

In this case, minimizing your expression (given that the sum is positive!) is just to minimize the sum, the square root and square are red herings ($(\sqrt{x} - 1)^2$ is monotone).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ They're not quite red herrings. The expression takes on value $0$ when you pick a subset $S$ such that $\Sigma_{i\in S} i = 1/2$, so you would think that the goal is to make $\Sigma_{i\in S} i$ as close to $1/2$ as possible (I guess this is what you mean). However, the square root messes this up; it gives preference to being an $\epsilon$ under $1/2$ as opposed to being $\epsilon$ above $1/2$. $\endgroup$ – Tom van der Zanden Feb 27 at 17:38
  • $\begingroup$ The function $f(x)=(\sqrt{x}-1)^2$ is not monotone increasing on $[0,\infty]$: it is monotone decreasing on $[0,1]$ and monotone increasing on $[1,\infty]$. $\endgroup$ – D.W. Feb 27 at 19:12

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.