<p>The problem is NP-Hard and the reduction is from partition. </p>

<p>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$.</p>

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

<p>$v_i = (x_i, -x_i, 0)$,</p>

<p>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$.</p>

<p>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</p>

<p>$(\alpha, 2t -\alpha, t)$. </p>

<p>Clearly, this vector is maximized when $\alpha=t$, as required. </p>

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

<p>QED</p>

<p>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).</p>

<h2>2d</h2>

<p>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...)</p>

CC BY-SA 2.5
2010-10-04T05:29:26.440Z
Thanks for your answer. I think it is strongly NP-complete by a reduction from 3-partition.
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-10-04T10:00:32.670Z
@turkistany ...only if you use unbounded dimension.
Sariel Har-Peled
CC BY-SA 2.5
2010-10-04T04:05:08.287Z
2010-10-04T09:59:23.907Z
2010-10-04T09:59:23.907Z
Sariel Har-Peled
<p>Input: a set $T$ of vectors $v_i=(x_i,y_i,z_i)$. Where $x_i,y_i,z_i$ are integers.</p>

<p>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) </p>

<blockquote>
  <p>Is this problem efficiently solvable or is it NP-hard?</p>
</blockquote>

<p>I'm not aware of results related to the 2D case. </p>

CC BY-SA 3.0
2015-09-02T18:02:06.620Z
@SarielHar-Peled, What about approximating it? I also have a [similar question](http://cs.stackexchange.com/questions/45718/2-dimensional-subset-sum-looking-for-information). It is easy to see that it is NP-hard and I believe NP-complete since it will have a polynomial certificate. I am intrested in approximation results. For this problem do you know any such result because I could not find anything. My current aim is for inapproximability. Any info would be helpful. Thnx
Harry
CC BY-SA 3.0
2015-09-03T20:04:18.610Z
The susbset approximation algorithms should work in this case. See Section 9.2 here: http://sarielhp.org/teach/notes/algos/files/09_approx_III.pdf
Sariel Har-Peled
CC BY-SA 2.5
2010-09-21T04:57:05.780Z
For clarification, you mean that the minimum among the projections to the axes is maximized?
arnab
CC BY-SA 2.5
2010-09-21T05:09:31.267Z
do you want to maximize the projection or its absolute value ?
Suresh Venkat
CC BY-SA 2.5
2010-09-21T05:26:26.213Z
could you please add these clarifications to the question
Suresh Venkat
CC BY-SA 2.5
2010-09-22T05:11:02.347Z
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}.
Vinayak Pathak
CC BY-SA 2.5
2010-09-22T05:15:30.670Z
Also, just an obvious observation - the 1D case is easy.
Vinayak Pathak
CC BY-SA 2.5
2010-09-25T04:45:52.103Z
Is it known to be hard in higher dimensions?
Sariel Har-Peled
CC BY-SA 2.5
2010-09-25T05:04:49.527Z
@Sariel, I'm not aware of such results.
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-10-04T03:32:07.090Z
If the dimension is unbounded then it seems easy to reduce this to partition or something similar. If the numbers are small, then dynamic programming would work in polynomial time. Thus, the hard variant seems when the numbers are super polynomial in size. If you allow numbers that are exponential (i.e., say linear or quadratic number of bits per number), it seems believable that some variant of partition can be reduced to this problem.
Sariel Har-Peled
CC BY-SA 2.5
2010-10-04T03:44:26.587Z
@Sariel, your idea is promising one. Do you think it is strongly NP-complete?
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-10-04T04:11:31.193Z
@turkistany... See answer below. I think it has exactly the same status as subset sum/partition.
Sariel Har-Peled
<cc.complexity-theory><np-hardness>
Complexity of finding vectors with optimal projection?
Mohammad Al-Turkistany
# Complexity of finding vectors with optimal projection?

(Asked by: username_0 on 2010-09-21)

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.

**Tags:** cc.complexity-theory, np-hardness
> **Comments:**
> **username_3**: For clarification, you mean that the minimum among the projections to the axes is maximized?  
> **username_4**: do you want to maximize the projection or its absolute value ?  
> **username_4**: could you please add these clarifications to the question  
> **username_5**: 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}.  
> **username_5**: Also, just an obvious observation - the 1D case is easy.  
> **username_2**: Is it known to be hard in higher dimensions?  
> **username_0**: @Sariel, I'm not aware of such results.  
> **username_2**: If the dimension is unbounded then it seems easy to reduce this to partition or something similar. If the numbers are small, then dynamic programming would work in polynomial time. Thus, the hard variant seems when the numbers are super polynomial in size. If you allow numbers that are exponential (i.e., say linear or quadratic number of bits per number), it seems believable that some variant of partition can be reduced to this problem.  
> **username_0**: @Sariel, your idea is promising one. Do you think it is strongly NP-complete?  
> **username_2**: @turkistany... See answer below. I think it has exactly the same status as subset sum/partition.  
> **username_1**: @SarielHar-Peled, What about approximating it? I also have a [similar question](http://cs.stackexchange.com/questions/45718/2-dimensional-subset-sum-looking-for-information). It is easy to see that it is NP-hard and I believe NP-complete since it will have a polynomial certificate. I am intrested in approximation results. For this problem do you know any such result because I could not find anything. My current aim is for inapproximability. Any info would be helpful. Thnx  
> **username_2**: The susbset approximation algorithms should work in this case. See Section 9.2 here: http://sarielhp.org/teach/notes/algos/files/09_approx_III.pdf  

---

## 1 answers

### Answer by username_2 on 2010-10-04. Score: 8 | Accepted answer

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...)

> **Comments:**
> **username_0**: Thanks for your answer. I think it is strongly NP-complete by a reduction from 3-partition.  
> **username_2**: @turkistany ...only if you use unbounded dimension.  

---

