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?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.