I do not know if this problems exists with a different name, if it is, I could not find it.
The problem is this:
Given a set $S$ of $n$ points in $\mathbb{Z}^2$, is there a subset $A\subset S$ such that the points of $A$ sum up to $(0,0)$?
If we restrict in $\mathbb{Z}$ this is the classic Subset-Sum problem. Furthermore this can be generalized in n-dimensions if all points are in $\mathbb{Z}^n$.
Since Subset-Sum is NP-complete so would be this problem thus, I am intrested in approximating it. (Here there is another issue, even for the classic Subset-Sum: since the target is $0$ how the approximation ratio be represented? Maybe using the largest integer or the mean of $S$?)
Subset-Sum has an FPTAS but I don't think that that is the case for the 2D Subset-Sum. One idea is to solve only in the $x$ dimension and from all the addmisable solutions pick the one that minimizes the sum in the $y$ dimension. But this cannot guarantee a ratio for the $y$ sum.
Does anyone has any information for me? Even bad news (inapproximability) are good news. The only close problem that I manage to locate is the Weighted Distribution problem (set of binary vector and ask if there is a subset that sums to the zero vector) coming from coding theory, proven to be $W[2]$-complete in this paper, thus not in EPTAS.
EDIT 1: Now I look at it again, I do not think that Weighted Distribution is similiar. It is more alike the classic Subset-Sum since every bit vector can just represent a number. Now I am looking at multidimensional Knapsack.
EDIT 2:An idea to tranform it to 1D-SS is to take the xx' (and after the yy' projections). The xx' projection will give you a good x value but for the y axis we cannot guarantee anything. Another approach, generalizing the classic SS aproximation idea (see here and here) is to create rings in $\mathbb{Z}^2$ but this also does not work good. Maybe if we take multiple projection and choose the best?
