Approximate subset sum with two-dimensional vectors
Let $\rm V$ be the $2 \times n$ matrix whose $i$-th column is vector $\rm v_i$. We have the Boolean optimization problem in $\mathrm z \in \{0,1\}^n$
$$\min_{\mathrm z \in \{0,1\}^n} \| \mathrm V \mathrm z + \mathrm w \|_2^2$$
Let
$$\rm z = \frac 12 (x + 1_n)$$
where $\mathrm x \in \{\pm 1\}^n$. Hence, we have an instance of the Boolean least-squares (BLS) problem
$$\min_{\mathrm x \in \{\pm 1\}^n} \| \mathrm A \mathrm x - \mathrm b \|_2^2$$
where
$$\rm A = \frac 12 V \qquad \qquad \qquad b = - \left( \frac 12 V 1_n + w \right)$$
Since $\{\pm 1\}$ is the solution set of the quadratic equation $x_i^2 = 1$, we have the following (non-convex) quadratically constrained quadratic program (QCQP) in $\mathrm x \in \mathbb R^n$
$$\begin{array}{ll} \text{minimize} &amp; \| \mathrm A \mathrm x - \mathrm b \|_2^2\\ \text{subject to} &amp; x_i^2 = 1 \quad \forall i \in \{1,2,\dots,n\}\end{array}$$
Exhaustive evaluation of the objective function at all $2^n$ points is only feasible for small $n$.

SDP relaxation
Note that
$$\begin{array}{rl} \| \mathrm A \mathrm x - \mathrm b \|_2^2 &amp;= (\mathrm A \mathrm x - \mathrm b)^{\top} (\mathrm A \mathrm x - \mathrm b)\\ &amp;= \mbox{tr} \left( (\mathrm A \mathrm x - \mathrm b)  (\mathrm A \mathrm x - \mathrm b)^{\top} \right)\\ &amp;= \mbox{tr} \left( \begin{bmatrix} \mathrm A &amp; -\mathrm b\end{bmatrix} \begin{bmatrix} \mathrm x\\ 1\end{bmatrix} \begin{bmatrix} \mathrm x\\ 1\end{bmatrix}^{\top} \begin{bmatrix} \mathrm A &amp; -\mathrm b\end{bmatrix}^{\top} \right)\\ &amp;= \mbox{tr} \left( \begin{bmatrix} \mathrm A^{\top}\\ -\mathrm b^{\top}\end{bmatrix} \begin{bmatrix} \mathrm A &amp; -\mathrm b\end{bmatrix} \begin{bmatrix} \mathrm x\\ 1\end{bmatrix} \begin{bmatrix} \mathrm x^{\top} &amp; 1\end{bmatrix} \right)\\ &amp;= \mbox{tr} \left( \begin{bmatrix} \,\,\,\, \mathrm A^{\top} \mathrm A &amp; -\mathrm A^{\top}\mathrm b\\ -\mathrm b^{\top}\mathrm A &amp; \,\,\,\, \mathrm b^{\top}\mathrm b\end{bmatrix} \begin{bmatrix} \mathrm x \mathrm x^{\top} &amp; \mathrm x\\ \mathrm x^{\top} &amp; 1\end{bmatrix} \right)\end{array}$$
Since $\mathrm x \in \{\pm 1\}^n$, all $n$ entries on the main diagonal of $\mathrm x \mathrm x^{\top}$ are equal to $1$. Thus,
$$\begin{bmatrix} \mathrm x \mathrm x^{\top} &amp; \mathrm x\\ \mathrm x^{\top} &amp; 1\end{bmatrix}$$
is symmetric, positive semidefinite and has only ones on its main diagonal, i.e., it is a correlation matrix. Its rank is $1$. Let
$$\mathrm C := \begin{bmatrix} \,\,\,\, \mathrm A^{\top} \mathrm A &amp; -\mathrm A^{\top}\mathrm b\\ -\mathrm b^{\top}\mathrm A &amp; \,\,\,\, \mathrm b^{\top}\mathrm b\end{bmatrix}$$
Hence, the BLS problem can be written as the following rank-constrained optimization problem in $(n+1) \times (n+1)$ symmetric matrix $\rm Y$
$$\begin{array}{ll} \text{minimize} &amp; \langle \mathrm C , \mathrm Y \rangle\\ \text{subject to} &amp; y_{ii} = 1, \quad \forall i \in \{1,2,\dots,n+1\}\\ &amp; \mathrm Y \succeq \mathrm O_{n+1}\\ &amp; \mbox{rank} (\mathrm Y) = 1\end{array}$$
which is a hard problem due to the rank constraint. Relaxing the optimization problem above by discarding the rank constraint, we then obtain the following semidefinite program (SDP) in $\rm Y$
$$\boxed{\begin{array}{ll} \text{minimize} &amp; \langle \mathrm C , \mathrm Y \rangle\\ \text{subject to} &amp; y_{ii} = 1, \quad \forall i \in \{1,2,\dots,n+1\}\\ &amp; \mathrm Y \succeq \mathrm O_{n+1}\end{array}}$$
which is convex and computationally tractable. This SDP relaxation provides a lower bound on the minimum of the original BLS problem. In the very, very fortunate case where the optimal solution of the SDP happens to be rank-$1$, we have solved the BLS problem.

References

Alexandre d'Aspremont, Stephen Boyd, Relaxations and Randomized Methods for Nonconvex QCQPs, EE392o, Stanford University, Autumn 2003.

Stephen Boyd, Convex Optimization, IAM-PIMS, Vancouver, 3/15/04.

Laurent El Ghaoui, Homework Assignment #1, EE227A, January 2012.

Semidefinite relaxation for Boolean least squares, Mathematics Stack Exchange.