5
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.