Dynamic Programming for NP-Hard Problems
Xiaodong Wang, Jun Tian · Procedia Engineering · 2011
This paper presents the extremely simple algorithms for NP-hard subset-sum like problems with the bitset class. The presented algorithms decrease the time and space complexity of dynamic programming algorithms by exploiting word parallelism. The computational experiments demonstrate that the achieved results are not only of theoretical interest, but also that the techniques developed may actually lead to considerably faster algorithms.