# Complexity of this minimization

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)$?

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.
• 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? – user66081 Dec 21 '15 at 18:25
• 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. – Linus Hamilton Dec 21 '15 at 18:39
• 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. – user66081 Dec 21 '15 at 21:03