5
$\begingroup$

Input: a set $T$ of vectors $v_i=(x_i,y_i,z_i)$. Where $x_i,y_i,z_i$ are integers.

Output: a subset of vectors $v_1,v_2,...,v_n$ with vector addition $m=\sum v_i$ such that the projection of $m$ on each axis is maximized. (maximize the absolute value of the minimum projection along any axis)

Is this problem efficiently solvable or is it NP-hard?

I'm not aware of results related to the 2D case.

$\endgroup$
  • $\begingroup$ For clarification, you mean that the minimum among the projections to the axes is maximized? $\endgroup$ – arnab Sep 21 '10 at 4:57
  • $\begingroup$ do you want to maximize the projection or its absolute value ? $\endgroup$ – Suresh Venkat Sep 21 '10 at 5:09
  • $\begingroup$ could you please add these clarifications to the question $\endgroup$ – Suresh Venkat Sep 21 '10 at 5:26
  • $\begingroup$ I think one good starting point would be to start with the 2D case where the co-ordinates of the vectors are drawn from the set {-1, 1}. $\endgroup$ – Vinayak Pathak Sep 22 '10 at 5:11
  • $\begingroup$ Also, just an obvious observation - the 1D case is easy. $\endgroup$ – Vinayak Pathak Sep 22 '10 at 5:15
8
$\begingroup$

The problem is NP-Hard and the reduction is from partition.

So, assume you are given an instance of partition $S=${$x_1,\ldots,x_n$}. Let $t = (\sum_{i=1}^n x_i) / 2$. The question is whether there is a subset of $S$ such that its sum is $t$.

To this end, let $v_0 = (0, 2t, t)$ be a special vector. For every number $x_i$, create the vector

$v_i = (x_i, -x_i, 0)$,

for $i=1,\ldots, n$. Now, the claim is that there is a subset of the vectors with sum $\geq (t, t, t)$ (in absolute value) if and only if there is a subset of $S$ that add up to $t$.

So, consider a subset $X \subseteq S$, with $\alpha = \sum_{x\in X}$. We have that the corresponding sum of vectors (together with the special vector $v_0$) is

$(\alpha, 2t -\alpha, t)$.

Clearly, this vector is maximized when $\alpha=t$, as required.

Note, that you must include the special vector $v_0$ - otherwise the third coordinate would be zero in the sum of vectors.

QED

Note, that the problem is solvable in polynomial time if the numbers are polynomially small, doing dynamic programming (like the one used for solving subset sum if the numbers are small).

2d

If you set the special vector to be $(8t, 10t)$ then the above reduction would work verbatim in two dimensions. (The constant $8$ here is somewhat arbitrary...)

$\endgroup$
  • $\begingroup$ Thanks for your answer. I think it is strongly NP-complete by a reduction from 3-partition. $\endgroup$ – Mohammad Al-Turkistany Oct 4 '10 at 5:29
  • $\begingroup$ @turkistany ...only if you use unbounded dimension. $\endgroup$ – Sariel Har-Peled Oct 4 '10 at 10:00

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.