7
$\begingroup$

Let $T = \{z_1, \ldots z_n\}$ be a finite set of complex numbers on the unit circle. I would like an algorithm which can quickly compute the nonempty subset $S \subset T$ which maximizes $$\left| \operatorname{Re}\left(\prod_{z \in S} z\right) \right|.$$ I suspect this problem may be NP-Hard, but I'm not sure. I'm fine with an algorithm which computes an approximately maximal product.

$\endgroup$
2
  • 3
    $\begingroup$ I suppose the subset $S$ should be nonempty. $\endgroup$ Feb 24 at 8:33
  • $\begingroup$ If you look for an approximation, do you need something that works well for small $n$ (say smaller than 10) or rather something that works well for larger n, say $n=100$, and in the latter case, are your $z_i$ approximately uniformly random or follow some other known distribution? $\endgroup$
    – quarague
    Feb 24 at 17:44

2 Answers 2

16
$\begingroup$

This is NP-hard, because the subset sum problem with target number zero is reducible to it.

Suppose we want to find a nonempty subset of an integer subset $\{x_1,\cdots,x_n\}$ that sums up to zero.

Then we can let $z_k=\exp(2\pi i (x_k/a))$ where $a=|x_1|+\cdots+|x_n|+1$. There is a choice of $z_k$s that achieves the maximum value $1$ iff the corresponding nonempty subset sums up to $0$.

$\endgroup$
5
$\begingroup$

If you write $z = \exp(2\pi i\theta_z)$ for arguments $\theta_z\in [0,1)$, then as $$\Re(\prod_{z\in S}z) = \Re(\exp(2\pi \sum_{z\in S}\theta_z)) = \cos(2\pi\sum_{z\in S}\theta_z).$$ the problem is equivalent to finding $S$ such that $\sum_{z\in S}\theta_z\bmod 1$ is closest to either of $0$ (when the absolute value is positive) or $1/2$ (when it is negative). If one assumes that all $\theta_z$ are rational, and moreover that for $N\in\mathbb{N}$ they are all of the form $\theta_z = a_z / n$ for $a_z\in[0,1,\dots,n-1]$, one can rewrite this as finding $S$ such that $\sum_{z\in S}a_z \bmod n$ is closest to $0$ or $n/2$.

This seems to be a modular version of the 0-1 knapsack (optimization) problem. This is a simultaneous generalization of the standard 0-1 knapsack problem in 2 ways

  1. there is a modular constraint --- the objective function is $\sum_{z\in S}a_z \bmod n$ rather than $\sum_{z\in S}a_z$, and
  2. it is an optimization problem rather than a decision problem.

If you only had one of these generalizations, casual searching would lead to known results. For example, if you knew that $\sum_{z\in S}a_z\bmod n = 0$ (or $n/2$) exactly, then there is a standard reduction to lattice problems, which is even efficient if the instance is "sparse" in a certain sense.

I expect one can similarly attack this problem by reducing it to SVP/CVP on a suitable lattice. As a brief sketch, if one defines the matrix

$$B =\begin{pmatrix} N &0&0 &\dots & 0\\ a_{z_1} & 1 & 0 & &0\\ a_{z_2} & 0 & 1 & \dots &0\\ \vdots &&&\ddots&\vdots\\ a_{z_k} & 0 & 0 & \dots & 1 \end{pmatrix},$$ Then one can check that any (integer) linear combination of the rows of the above takes the form

$$ \begin{pmatrix} Nx_0 + a_{z_1}x_1 + \dots + a_{z_k}x_k\\ x_1\\ \vdots\\ x_k \end{pmatrix} $$ where $\vec x = (x_0,\dots, x_k)\in\mathbb{Z}^{k+1}$. Clearly, the norm of this is minimized for $\vec x = 0$. One can argue that the shortest non-zero vector will lead to $Nx_0 + \sum_i a_{z_i}x_i$ being small. There is still of course work to do (for example, the shortest vector in the aforementioned lattice may lead to a "solution" to a knapsack problem without 0/1 weights. This could plausibly be fixed by using a lattice basis with $M$ on the diagonal instead of $1$, to penalize choosing $x_1,\dots, x_k > 1$). Still, I expect a solution to your problem will proceed in a route similar to this, as this is fairly typical for "modular knapsack" problems.

$\endgroup$

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.