Pick matrices such that each partial sum is positive

Question

There is a sequence of $n$ sets, each set contains a constant number of constant-size vectors, e.g:

• $\{M_{1,1},M_{1,2},M_{1,3},M_{1,4}\}$
• $\{M_{2,1},M_{2,2},M_{2,3},M_{2,4}\}$
• ...
• $\{M_{n,1},M_{n,2},M_{n,3},M_{n,4}\}$

The task is to pick, from each set, a single vector, such that the sum of vectors and all the partial sums have no negative elements, i.e, select $i1,i2,...,in$ such that the following vectors:

• $M_{1,i1},ドル
• $M_{1,i1} + M_{2,i2},ドル
• $M_{1,i1} + M_{2,i2} + M_{3,i3},ドル
• ...

have only non-negative elements.

Is anything known about this problem?

• xavierm02: If you replace your matrices by vectors, the problem remains exactly the same.
• Erel Segal-Halevi: @xavierm02 you are right, and it looks better with vectors.
• xavierm02: It's NP-complete. NP is easy. NP-hard because you can reduce 4ドル-SAT$ to it.

Answer 1

I'll represent you problem as:

Let $S_1, \dots, S_n$ be sets of $p$ vectors of size $d$. Find a vector $v_i$ in each $S_i$ so that for every $k\le n,ドル $\displaystyle \sum\limits_{0\le i \le k}v_i$ has only non-negative coordinates.

Prop: This problem is in NP.

Proof: Once we have the set of indices / vectors, it's easy to check that they work in polynomial time.

---

Prop: For $d\ge 2$ constant and $p\ge 2$ constant, the problem (where $n$ is not bounded) is NP-hard.

Proof: We take an instance of the subset-sum problem, which is NP-hard. We have integers $i_1, \dots, i_n$. We define $M=|i_1|+\dots + |i_n|$.

We take $S_0=\{[M,M]\}$. For 1ドル\le k\le n,ドル $S_k=\{[i_k, -i_k],[0, 0]\}$ and $S_{n+1}=\{[-|M|, -|M|]\}$.

All the partial sums will clearly be $\ge 0$ except maybe the last one. The last one will be $\ge 0$ iff $\sum i_k\ge 0$ and $\sum -i_k\ge 0,ドル i.e. iff $\sum i_k = 0$. So there is a solution iff the subset sum instance has one.

---

The following is a weaker result but it's written so I leave it here.

Prop: This problem with 2ドルn$ sets of $p$ vectors of size 2ドルd$ is at least as hard as $CNF-SAT$ on $n$ clauses with $p$ literals per clause and $d$ variables.

Proof: Take a set $C_1,\dots, C_n$ of clauses on $d$ variables, with $p$ literals per clause. $C_i=l_{i,1}\lor \dots \lor l_{i,p}$.

We write $v_k$ for the $k$th variable. To a positive literal $l_{i,j}=v_k,ドル we associate the vector $\phi(v_k)$ of dimension 2ドルd$ that has a 1ドル$ at the $k$th position and 0ドル$s everywhere else. To a negative literal $l_{i,j}=\lnot v_j$ we associate the vector $\phi(v_k)$ of dimension 2ドルd$ with a 1ドル$ in $d+k$th position and zeros everywhere else.

Now, for 1ドル\le k \le n,ドル we set $S_i=\{n\phi(v_k),n\phi(\lnot v_k)\}$ (and we add some useless vectors with big negative values if you really want the set to have size $p$). For 1ドル\le i\le n,ドル we set $S_{n+k}=\{-\phi(l_{i,j}) / j\in\{1,\dots,n\}\}$.

The idea is the following. In the first $n$ coordinates, we store how many times we can use each of the variable, and in the next $n$ coordinates, we store how many times we can use each of the negation of variables. Then, at the beginning, in the first $n$ sets, we pick for each variable if it's true or false (by adding $n$ to the number of times we can use the variable, or to the number of times we can use its negation). The last $n$ sets then use the variables / negations to make the clause true. To make a clause true, you need to make one literal true, and the true ltterals will be exactly those for which the corresponding coordinate is $>0$ so that you can subtract 1ドル$ while remaining $\ge 0$. If you chose $v_k$ to be false, the corresponding coordinate will remain 0ドル$ for the whole thing so if you try to use it, it will become $<0$. And we add $n$ at the beginning because since there are $n$ clauses, we won't subtract more than $n$.

Prop: For $p\ge 3,ドル the problem (where $d$ and $n$ are not bounded) is $NP$-hard.

Proof: The reduction given above reduces 3ドル-SAT$ to it in polynomial time. And 3ドル-SAT$ is NP-hard.