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$

1 Answer 1

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$
4
  • $\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, 2015 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$ Dec 21, 2015 at 18:39
  • 1
    $\begingroup$ Simpler explanation follows from the AM-GM inequality. $\endgroup$ Dec 21, 2015 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, 2015 at 21:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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