I think it is still open

First a disclaimer: I am no expert on this problem.. I heard it awhile ago, liked it, wrote it down, and that's what you see here. However, I do believe it is still open. If my understanding is correct, the problem considered in the paper you mention ("Efficient approximation algorithms for the subset-sums equality problem" by Bazgan, Santha and Tuza, JCSS Vol.64 Issue 2, March 2002) is a relaxed version of the one stated here where the restriction $ \sum_{i=1}^n a_i < 2^n - 1 $ is not present, and the goal is to find a pair of nonempty disjoint subsets $ I,J \subseteq \{1,\ldots,n\} $ so that $ \sum_{i \in I} a_i $ and $ \sum_{j \in J} a_j $ are as close as possible. I believe the only hardness results they obtain are for this problem.

The thing still missing is what to do with the funny assumption $ \sum_{i=1}^n a_i < 2^n - 1 $. Although the problem is a search problem which looks roughly like a knapsack-type problem (and thus should be NP-hard), the associated decision problem is trivially "true", yet there is no obvious way to use this information.

PS: thanks for the post!


Comments are limited to a maximum of 1000 characters.
More information about formatting options