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?

  • 6
    $\begingroup$ What is TC? ${}$ $\endgroup$ – Emil Jeřábek Jan 10 at 10:08
  • 3
    $\begingroup$ Looks like time complexity. There is not enough information here. You can always publish it and working on the next iteration. $\endgroup$ – Chao Xu Jan 10 at 13:52
  • 1
    $\begingroup$ @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 $\endgroup$ – John Seppard Jan 10 at 14:23
  • 2
    $\begingroup$ 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 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 $\endgroup$ – Phylliida Jan 10 at 15:37
  • 4
    $\begingroup$ @Phylliida Wouldn't that be $O(2^{n/2}/\sqrt{n})$? $\endgroup$ – Clement C. Jan 11 at 3:17

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.