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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\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
    Commented 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$
    – Linus Hamilton
    Commented Dec 21, 2015 at 18:39
  • 1
    $\begingroup$ Simpler explanation follows from the AM-GM inequality. $\endgroup$
    – Max Alekseyev
    Commented 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
    Commented Dec 21, 2015 at 21:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .