What is the reason why nobody has combined the 'meet in the middle' approach with the Dynamic Programming for subset sum?

I found it curious that is a kind of a open problem.. as a matter of fact I never have seen both them combined.

On a paper (1), the author questions if by their combination would be possible to obtain an algorithm with time complexity $O(T^{1/2}*n^{O(1)})$.

Is that time complexity something reasonable?

Could it get better or worse than the above estimation?

(1) SETH-Based Lower Bounds for Subset Sum and Bicriteria Path, Amir Abboud et al. arXiv:1704.04546

  • $\begingroup$ I think that in the first sentence you mean "nobody" rather than "anybody". $\endgroup$ – Yuval Filmus Nov 26 '17 at 12:25
  • $\begingroup$ Perhaps people have tried and failed? $\endgroup$ – Yuval Filmus Nov 26 '17 at 12:25
  • $\begingroup$ (edited the question to correct my mistake) $\endgroup$ – John Seppard Nov 26 '17 at 18:49
  • $\begingroup$ @Yuval perhaps, another possibility, is , if somebody found how to do it, that the final time complexity was not the one expected, do this count as a failure? $\endgroup$ – John Seppard Nov 26 '17 at 19:45
  • $\begingroup$ Any improvement on the state-of-the-art would have been published. That's how our community works. $\endgroup$ – Yuval Filmus Nov 26 '17 at 20:31

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.