4
$\begingroup$

For integer $N$ consider the mapping $$f : (0,1)^N \to \mathbb{R}, \quad x \mapsto \min_{b \in \{0,1\}^N} \left\{ x^b + x^{1-b} \right\},$$ where $x^b = x_1^{b_1} \cdots x_N^{b_N}$ and $1-b = (1-b_1, \ldots, 1-b_N)$. Note that $x$ is a vector of reals and $b$ is a binary vector.

Is there a faster than $O(2^N)$ algorithm (worst-case in $x$) for computing $f(x)$?

$\endgroup$
5
$\begingroup$

To minimize $x^b + x^{1-b}$, we must find $b$ such that $x^b$ and $x^{1-b}$ are as close together as possible.

Taking logs, this is equivalent to partitioning $(\log(x_1), \log(x_2), \dots, \log(x_n))$ into two subsets whose sums are as close together as possible. This is the well-known subset-sum problem, which is $\mathsf{NP}$-complete in general, but has polytime approximation algorithms.

$\endgroup$
  • $\begingroup$ If the sums of logs are to be as close as possible, the ratio $x^b / x^{1-b}$ should be close to one. Why is this the right condition? $\endgroup$ – user66081 Dec 21 '15 at 18:25
  • 1
    $\begingroup$ Because $x^b+x^{1-b}=\left(\sqrt{x^{b}}-\sqrt{x^{1-b}}\right)^{2}+2\sqrt{x^{1}}$. Since $x^1$ does not depend on $b$, minimizing this is equivalent to minimizing $|\sqrt{x^{b}}-\sqrt{x^{1-b}}|$. Which is the same as getting $x^b$ and $x^{1-b}$ as close together as possible. $\endgroup$ – Linus Hamilton Dec 21 '15 at 18:39
  • 1
    $\begingroup$ Simpler explanation follows from the AM-GM inequality. $\endgroup$ – Max Alekseyev Dec 21 '15 at 18:51
  • 1
    $\begingroup$ I was missing the following bit. Write $\alpha = x^b$ and $\beta = x^{1-b}$, and note that $\alpha \beta = {const}$. Then $(\alpha + \beta) \mapsto |\log(\alpha/\beta)|$ is nondecreasing. $\endgroup$ – user66081 Dec 21 '15 at 21:03

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.