<p>Has a SUBSET-SUM &quot;with error&quot; variant been studied - and with error, I mean, instead of a single target value <span class="math-container">$k$</span>, a target <em>interval</em> <span class="math-container">$[k-\varepsilon,k+\varepsilon]$</span> (<span class="math-container">$\varepsilon&gt;0$</span> very small)? <strong>EDIT:</strong> In this variant, the input is positive <strong>real numbers</strong> rather than integers.</p>
<p>if so....</p>
<ol>
<li>Is this weaker variant still NP-Hard?</li>
<li>Suppose we turn this variant into a search promise problem; we're guaranteed the input multiset has a subset whose sum is in <span class="math-container">$[k-\varepsilon,k+\varepsilon]$</span>, and we would like to <strong>find</strong> the witnessing subset. Is this NP-Hard?</li>
</ol>
<p>Any links/resources (papers/books/etc) that discuss this problem would also be appreciated. Thank you.</p>

CC BY-SA 4.0
2022-03-11T10:54:23.417Z
If $\epsilon<1$, then the error variant coincides with the original SUBSET SUM problem. If $\epsilon$ is some fixed real number, then the error variant coincides with a scaled version of SUBSET SUM. Hence all these variants are NP-hard.
Gamow
CC BY-SA 4.0
2022-03-11T15:51:43.010Z
Oh shoot I forgot a key detail; in this variant, input comes from positive reals, not positive integers.
CSSTUDENT
CC BY-SA 4.0
2022-03-11T16:13:31.113Z
For 1. Integers is a subset of real numbers (this is the point of Gamow). 

For 2. NP-hardness is defined for decision problems not for witness extraction but I understand what you mean. Let us suppose that you have a witness extraction algorithm that run in polynomial time $P(n)$ for an input of size $n$ that has a sum in $[k-\epsilon;k+\epsilon]$.   You can run this algorithm on any instance and stop it after $P(n)$ and check whether the witness is correct (this supposes that you know $P$).
Louis
CC BY-SA 4.0
2022-03-11T18:44:55.820Z
If the input is from the reals, is this still on a Turing machine model with numbers in floating point, or is it some real-valued machine that can do additions in O(1) time, etc.?
Jake
CC BY-SA 4.0
2022-03-11T19:12:00.643Z
@jake the latter
CSSTUDENT
CC BY-SA 4.0
2022-03-14T19:20:27.230Z
related: https://cs.stackexchange.com/questions/147724/a-dynamic-program-to-decide-whether-the-solution-is-in-a-given-range.   See the comments there for an algorithm that can find a subset with sum in $[k, k(1+\epsilon)]$ (if one exists) in time $n^{O(1/\epsilon)}$ (polynomial for fixed $\epsilon$).  BTW why not make the input rational numbers?  Then you could use the standard model of computation.  BTW do you really mean *multiset*?  Typically subset-sum doesn't allow repetitions, and allowing them changes the problem substantially.
Neal Young
CC BY-SA 4.0
2022-03-15T15:54:24.533Z
@NealYoung Does multiset ease things up?
Turbo
CC BY-SA 4.0
2022-03-15T21:53:51.133Z
For your problem?  I'm not sure it makes it easier, but it seems to change the problem significantly.  E.g., in the case that there is an element of size at most $2\epsilon$, repeating just that element the right number of times will give a multiset with total in $[k-\epsilon, k+\epsilon]$...  For Subset Sum the multi-set version is "Making Change" and is [apparently](https://cstheory.stackexchange.com/questions/8970/complexity-of-a-subset-sum-variant) NP-hard.  (Indeed it seems easy to reduce subset-sum to Making Change using standard techniques to ensure each element is used at most once.)
Neal Young
CC BY-SA 4.0
2022-03-16T07:34:26.937Z
@NealYoung thanks for the comment. Yes I really did mean multiset.
CSSTUDENT
CC BY-SA 4.0
2022-03-16T13:35:58.677Z
Okay, well your problem as stated is NP-hard (more or less as observed above in the comments, even for $\epsilon=1$), as it generalizes Making Change.  This seems to answer the question in your post.  If you want any more refined information (e.g. is there a PTAS, etc) you'll need to update your post or post a new question.
Neal Young
<np-hardness>
SUBSET SUM "with error"
CSSTUDENT
# SUBSET SUM "with error"

(Asked by: username_0 on 2022-03-11)

Has a SUBSET-SUM "with error" variant been studied - and with error, I mean, instead of a single target value $k$, a target *interval* $[k-\varepsilon,k+\varepsilon]$ ($\varepsilon>0$ very small)? **EDIT:** In this variant, the input is positive **real numbers** rather than integers.

if so....

1. Is this weaker variant still NP-Hard?
2. Suppose we turn this variant into a search promise problem; we're guaranteed the input multiset has a subset whose sum is in $[k-\varepsilon,k+\varepsilon]$, and we would like to **find** the witnessing subset. Is this NP-Hard?

Any links/resources (papers/books/etc) that discuss this problem would also be appreciated. Thank you.

**Tags:** np-hardness

> **Comments:**
> **username_1**: If $\epsilon<1$, then the error variant coincides with the original SUBSET SUM problem. If $\epsilon$ is some fixed real number, then the error variant coincides with a scaled version of SUBSET SUM. Hence all these variants are NP-hard.  
> **username_0**: Oh shoot I forgot a key detail; in this variant, input comes from positive reals, not positive integers.  
> **username_2**: For 1. Integers is a subset of real numbers (this is the point of username_1).   For 2. NP-hardness is defined for decision problems not for witness extraction but I understand what you mean. Let us suppose that you have a witness extraction algorithm that run in polynomial time $P(n)$ for an input of size $n$ that has a sum in $[k-\epsilon;k+\epsilon]$.   You can run this algorithm on any instance and stop it after $P(n)$ and check whether the witness is correct (this supposes that you know $P$).  
> **username_3**: If the input is from the reals, is this still on a Turing machine model with numbers in floating point, or is it some real-valued machine that can do additions in O(1) time, etc.?  
> **username_0**: @jake the latter  
> **username_4**: related: https://cs.stackexchange.com/questions/147724/a-dynamic-program-to-decide-whether-the-solution-is-in-a-given-range.   See the comments there for an algorithm that can find a subset with sum in $[k, k(1+\epsilon)]$ (if one exists) in time $n^{O(1/\epsilon)}$ (polynomial for fixed $\epsilon$).  BTW why not make the input rational numbers?  Then you could use the standard model of computation.  BTW do you really mean *multiset*?  Typically subset-sum doesn't allow repetitions, and allowing them changes the problem substantially.  
> **username_5**: @NealYoung Does multiset ease things up?  
> **username_4**: For your problem?  I'm not sure it makes it easier, but it seems to change the problem significantly.  E.g., in the case that there is an element of size at most $2\epsilon$, repeating just that element the right number of times will give a multiset with total in $[k-\epsilon, k+\epsilon]$...  For Subset Sum the multi-set version is "Making Change" and is [apparently](https://cstheory.stackexchange.com/questions/8970/complexity-of-a-subset-sum-variant) NP-hard.  (Indeed it seems easy to reduce subset-sum to Making Change using standard techniques to ensure each element is used at most once.)  
> **username_0**: @NealYoung thanks for the comment. Yes I really did mean multiset.  
> **username_4**: Okay, well your problem as stated is NP-hard (more or less as observed above in the comments, even for $\epsilon=1$), as it generalizes Making Change.  This seems to answer the question in your post.  If you want any more refined information (e.g. is there a PTAS, etc) you'll need to update your post or post a new question.  

---

## 0 answers

