<p>I don't know if it has an official name, but it is NP complete; I give a reduction idea from Exact Cover from 3-Sets:</p>
<p>Given <span class="math-container">$n = 3q$</span>, <span class="math-container">$X = \{x_1,...,x_{n}\}$</span> and <span class="math-container">$C_1,C_2,...,C_m$</span> a collection of 3 elements subsets.</p>
<p>Use the following set of <span class="math-container">$3q + 2$</span> dimensions vectors:</p>
<p><span class="math-container">$v_{fill} = [1_1, 1_2, ... ,1_{3q}, \; q_z ,\; 0_b]$</span> (the subscripts are just labels to show the element &quot;column&quot; position)</p>
<p>For each <span class="math-container">$C_i = \{ x_{i1}, x_{i2}, x_{i3} \}$</span></p>
<p><span class="math-container">$v_{C_i} =  [ 0,...,0, -1_{i1},0,...,0,-1_{i2},0,-1_{i3},0,...,0, \; -1_{z}, \; 1_{b} ]$</span></p>
<p><span class="math-container">$v_{clean} = [ m, m, ..., m, m_{z}, -q_{b} ] $</span></p>
<p>Starting from <span class="math-container">$[0,0,...,0,\; 0_{z}, \; 0_{b}]$</span> the only vector that doesn't contain negative elements is <span class="math-container">$v_{fill}$</span> so it must be the first of the sum.</p>
<p>Then in order to be able to add <span class="math-container">$v_{clean}$</span> that has a <span class="math-container">$-q$</span> in column <span class="math-container">$b$</span>; we must add exactly <span class="math-container">$q$</span> vectors <span class="math-container">$v_{C_i}$</span> that contains <span class="math-container">$[....,1_{b}]$</span>; we cannot add more than <span class="math-container">$q$</span> otherwisee the column <span class="math-container">$z$</span> becomes negative.</p>
<p>Furthermore we cannot add two <span class="math-container">$C_i$</span> that has the same element in the first <span class="math-container">$3q$</span> columns, otherwise it would become negative.</p>
<p>At this point <span class="math-container">$v_{clean}$</span> can be added; and, finally, the remaining <span class="math-container">$v_{C_i}$</span> can be added (&quot;cleaned&quot;)</p>
<p>Example:</p>
<pre><code>n = 3q = 6; q=2; m = 3
C_1={1,2,3}, C_2={ 4,5,6}, C_3={1,2,4}
v_fill = [ 1, 1, 1, 1, 1, 1, 2, 0 ]
v_C_1  = [ 1, 1, 1, 0, 0, 0,-1, 1 ]
v_C_2  = [ 0, 0, 0, 1, 1, 1,-1, 1 ]
v_C_3  = [ 1, 1, 0, 1, 0, 0,-1, 1 ]
v_clear= [ 3, 3, 3, 3, 3, 3, 3,-2 ]

Sum: v_fill + v_C_1 + v_C_2 + v_clear + v_C_3
</code></pre>

CC BY-SA 4.0
2024-01-09T10:53:49.417Z
2024-01-09T11:00:50.453Z
2024-01-09T11:00:50.453Z
Marzio De Biasi
<p>Consider we are given a collection of <span class="math-container">$n$</span> vectors in <span class="math-container">$d$</span> dimensions, we want to decide if they can be rearranged into <span class="math-container">$v_1,\ldots,v_n$</span> such that <span class="math-container">$\sum_{i=1}^j v_i\geq \textbf{0}$</span> for all <span class="math-container">$j\in [n]$</span>. Here <span class="math-container">$a \geq \textbf{0}$</span> if and only if all coordinates is at least <span class="math-container">$0$</span>.</p>
<p>Have this problem been studied before?</p>

<ds.algorithms><reference-request>
Rearrange vectors so partial sums are all non-negative
Chao Xu
# Rearrange vectors so partial sums are all non-negative

(Asked by: username_0 on 2024-01-09)

Consider we are given a collection of $n$ vectors in $d$ dimensions, we want to decide if they can be rearranged into $v\_1,\ldots,v\_n$ such that $\sum\_{i=1}^j v\_i\geq \textbf{0}$ for all $j\in [n]$. Here $a \geq \textbf{0}$ if and only if all coordinates is at least $0$.

Have this problem been studied before?

**Tags:** ds.algorithms, reference-request

---

## 1 answers

### Answer by username_1 on 2024-01-09. Score: 3 | Accepted answer

I don't know if it has an official name, but it is NP complete; I give a reduction idea from Exact Cover from 3-Sets:
Given $n = 3q$, $X = \{x_1,...,x_{n}\}$ and $C_1,C_2,...,C_m$ a collection of 3 elements subsets.
Use the following set of $3q + 2$ dimensions vectors:
$v_{fill} = [1_1, 1_2, ... ,1_{3q}, \; q_z ,\; 0_b]$ (the subscripts are just labels to show the element "column" position)
For each $C_i = \{ x_{i1}, x_{i2}, x_{i3} \}$
$v_{C_i} =  [ 0,...,0, -1_{i1},0,...,0,-1_{i2},0,-1_{i3},0,...,0, \; -1_{z}, \; 1_{b} ]$
$v_{clean} = [ m, m, ..., m, m_{z}, -q_{b} ] $
Starting from $[0,0,...,0,\; 0_{z}, \; 0_{b}]$ the only vector that doesn't contain negative elements is $v_{fill}$ so it must be the first of the sum.
Then in order to be able to add $v_{clean}$ that has a $-q$ in column $b$; we must add exactly $q$ vectors $v_{C_i}$ that contains $[....,1_{b}]$; we cannot add more than $q$ otherwisee the column $z$ becomes negative.
Furthermore we cannot add two $C_i$ that has the same element in the first $3q$ columns, otherwise it would become negative.
At this point $v_{clean}$ can be added; and, finally, the remaining $v_{C_i}$ can be added ("cleaned")
Example:
n = 3q = 6; q=2; m = 3
C_1={1,2,3}, C_2={ 4,5,6}, C_3={1,2,4}
v_fill = [ 1, 1, 1, 1, 1, 1, 2, 0 ]
v_C_1  = [ 1, 1, 1, 0, 0, 0,-1, 1 ]
v_C_2  = [ 0, 0, 0, 1, 1, 1,-1, 1 ]
v_C_3  = [ 1, 1, 0, 1, 0, 0,-1, 1 ]
v_clear= [ 3, 3, 3, 3, 3, 3, 3,-2 ]

Sum: v_fill + v_C_1 + v_C_2 + v_clear + v_C_3


---

