I was doing a quick search for background on this question and came across this article: http://dx.doi.org/10.1006/jcss.2001.1784 , "Efficient approximation algorithms for the subset-sums equality problem" by Bazgan, Santha and Tuza, JCSS Vol.64 Issue 2 (March 2002). I only have access to the abstract, so I might be misinterpreting this, but they say, "... On the other hand, we show that in the case where the value of a solution is the positive difference between the two partial sums, the problem is not 2nk -approximable in polynomial time unless P = NP, for any constant k." I take this to mean that there are no exact polynomial time algorithms unless P=NP. If so, this problem is only open in the sense that any question reducible to P vs. NP can be considered open.
login/create account
Drupal
CSI of Charles University
Should this problem still be considered open?
I was doing a quick search for background on this question and came across this article: http://dx.doi.org/10.1006/jcss.2001.1784 , "Efficient approximation algorithms for the subset-sums equality problem" by Bazgan, Santha and Tuza, JCSS Vol.64 Issue 2 (March 2002). I only have access to the abstract, so I might be misinterpreting this, but they say, "... On the other hand, we show that in the case where the value of a solution is the positive difference between the two partial sums, the problem is not 2nk -approximable in polynomial time unless P = NP, for any constant k." I take this to mean that there are no exact polynomial time algorithms unless P=NP. If so, this problem is only open in the sense that any question reducible to P vs. NP can be considered open.