Reduction: ZOE → Subset Sum

ZOE:

Given $A$ , find $\vec{x}$ consisting of 0-1 entries that

A\vec{x} = \vec{1}

Subset Sum:

Special case of Knapsack

Every value of item $i$ equals to its weight $v_i = w_i$

Find a subset of item $i$ that sum of their values equals to exactly $W$

Reduction with two special cases of ILP:

One with many equations but only 0-1 coefficients

The other with a single equation but arbitrary integer coefficients

Reduction based on the idea that: $0-1$ vectors can encode numbers!

We’re looking for a set of columns of $A$ that added together can make up a vector of all 1s.

A = \begin{bmatrix} 1 &0 &0 &0 \\ 0 &0 &0 &1 \\ 0 &1 &1 &0 \\ 1 &0 &0 &0 \\ 0 &1 &0 &0 \end{bmatrix}

Think columns as binary integers (from top to bottom), we’re looking for a subset of the inegers $10010_2 = 18, 00101_2 = 5, 00100_2 = 4, 01000_2 = 8$ that add up to $11111_2 = 31$ .

But one thing spoils the connection between 0-1 vectors and binary integers: CARRY.

$00101_2 + 00110_2 + 10100_2 = 11111_2$ even when the sum of corresponding vectors is not $(1,1,1,1,1)$ .

Easy to fix: think of column vectors not as integers in base 2, but in base $n+1$ ⇒ one more than # of columns
- At most $n$ integers added, there can be no carry