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$
12
  • $\begingroup$ For clarification, you mean that the minimum among the projections to the axes is maximized? $\endgroup$
    – arnab
    Sep 21, 2010 at 4:57
  • $\begingroup$ do you want to maximize the projection or its absolute value ? $\endgroup$ Sep 21, 2010 at 5:09
  • $\begingroup$ could you please add these clarifications to the question $\endgroup$ Sep 21, 2010 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$ Sep 22, 2010 at 5:11
  • $\begingroup$ Also, just an obvious observation - the 1D case is easy. $\endgroup$ Sep 22, 2010 at 5:15

1 Answer 1

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$
2
  • $\begingroup$ Thanks for your answer. I think it is strongly NP-complete by a reduction from 3-partition. $\endgroup$ Oct 4, 2010 at 5:29
  • $\begingroup$ @turkistany ...only if you use unbounded dimension. $\endgroup$ Oct 4, 2010 at 10:00

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.