<p>I have been working on a new approach for a subset sum exact solver, and the current state provides an algorithm operating on <span class="math-container">$O{n/2 \choose n/4}$</span>, demonstrating as well the hardest target value is not <span class="math-container">$\approx \frac{sum(S)}{2}$</span> but <span class="math-container">$\approx\frac{sum(S)}{4}$</span> for dense instances (<span class="math-container">$d \approx 1$</span>) in all cases.</p>

<p>I asked several people about their opinion and I got mixed feedback, some people though it was worth it to keep pushing the approach before publishing (to try to obtain an improved result, given this is likely possible, then publish), while other people encouraged me to publish right away given the improvement over the <span class="math-container">$O(2^{\frac{n}{2}})$</span> approach and the new characterization for the hardest target values not demonstrated before in the available literature, then continue working looking to improve these results.</p>

<p>What are your suggestions/opinions? </p>

CC BY-SA 4.0
2019-01-10T10:08:54.423Z
What is TC? ${}$
Emil Jeřábek
CC BY-SA 4.0
2019-01-10T13:52:55.097Z
Looks like time complexity. There is not enough information here. You can always publish it and working on the next iteration.
Chao Xu
CC BY-SA 4.0
2019-01-10T14:23:34.450Z
@ChaoXu, thank you for the suggestion and sorry for the lack of information but I don't think this is a place for paper reviews/was not looking for such thing
John Seppard
CC BY-SA 4.0
2019-01-10T14:26:45.873Z
Emil, removed the term to set the focus on the question, looks like that was a distraction, thanks!
John Seppard
CC BY-SA 4.0
2019-01-10T15:37:46.710Z
I don't have an answer to your question but personally I do find such a result interesting. For curious readers you can use [Stirling's approximation](https://en.wikipedia.org/wiki/Stirling%27s_approximation) to get $O({n/2 \choose n/4})$ $= O(\frac{2^{n/2}}{n})$, which imo provides a nicer comparison to the previous best algorithm
Phylliida
CC BY-SA 4.0
2019-01-10T17:27:55.517Z
My opinion is that it is better to keep pushing the approach to get the best possible results before publishing, but I believe this question is mostly a matter of personal preference than anything else. So do what you find most comfortable to do.
Emil Jeřábek
CC BY-SA 4.0
2019-01-10T17:31:54.947Z
By the way, when you say that "the hardest target value is $\approx\frac{sum(S)}4$", do you really mean it, so that e.g. you can give a polytime reduction of the general case to the $\frac{sum(S)}4$ case or something like that, or do you only mean that your algorithm takes the most time in this case?
Emil Jeřábek
CC BY-SA 4.0
2019-01-11T03:17:40.763Z
@Phylliida Wouldn't that be $O(2^{n/2}/\sqrt{n})$?
Clement C.
CC BY-SA 4.0
2019-01-15T09:51:03.083Z
@ClementC. just checked my math, you're right, thanks! (sorry I can't edit my comment or I would)
Phylliida
CC BY-SA 4.0
2019-01-16T22:52:46.493Z
@EmilJeřábek, I totally meant it.Thank you for sharing your opinion as well, and I'm leaning to what you suggest.
John Seppard
<np-complete><subset-sum>
new subset sum approach results
John Seppard
# new subset sum approach results

(Asked by: username_0 on 2019-01-09)

I have been working on a new approach for a subset sum exact solver, and the current state provides an algorithm operating on $O{n/2 \choose n/4}$, demonstrating as well the hardest target value is not $\approx \frac{sum(S)}{2}$ but $\approx\frac{sum(S)}{4}$ for dense instances ($d \approx 1$) in all cases.

I asked several people about their opinion and I got mixed feedback, some people though it was worth it to keep pushing the approach before publishing (to try to obtain an improved result, given this is likely possible, then publish), while other people encouraged me to publish right away given the improvement over the $O(2^{\frac{n}{2}})$ approach and the new characterization for the hardest target values not demonstrated before in the available literature, then continue working looking to improve these results.

What are your suggestions/opinions?

**Tags:** np-complete, subset-sum

> **Comments:**
> **username_1**: What is TC? ${}$  
> **username_2**: Looks like time complexity. There is not enough information here. You can always publish it and working on the next iteration.  
> **username_0**: @ChaoXu, thank you for the suggestion and sorry for the lack of information but I don't think this is a place for paper reviews/was not looking for such thing  
> **username_0**: Emil, removed the term to set the focus on the question, looks like that was a distraction, thanks!  
> **username_3**: I don't have an answer to your question but personally I do find such a result interesting. For curious readers you can use [Stirling's approximation](https://en.wikipedia.org/wiki/Stirling%27s_approximation) to get $O({n/2 \choose n/4})$ $= O(\frac{2^{n/2}}{n})$, which imo provides a nicer comparison to the previous best algorithm  
> **username_1**: My opinion is that it is better to keep pushing the approach to get the best possible results before publishing, but I believe this question is mostly a matter of personal preference than anything else. So do what you find most comfortable to do.  
> **username_1**: By the way, when you say that "the hardest target value is $\approx\frac{sum(S)}4$", do you really mean it, so that e.g. you can give a polytime reduction of the general case to the $\frac{sum(S)}4$ case or something like that, or do you only mean that your algorithm takes the most time in this case?  
> **username_4**: @username_3 Wouldn't that be $O(2^{n/2}/\sqrt{n})$?  
> **username_3**: @ClementC. just checked my math, you're right, thanks! (sorry I can't edit my comment or I would)  
> **username_0**: @EmilJeřábek, I totally meant it.Thank you for sharing your opinion as well, and I'm leaning to what you suggest.  

---

## 0 answers

