New to this forum, so please let me know if my question format is incorrect.For linear KP with $n$ items and $c$ capacity, dynamic programming can find exact solutions in $\mathcal{O}(nc)$. I have seen some results extending dynamic programming to approximate solutions to the QKP link giving a lower bound within 0.05% of true solutions in $\mathcal{O}(n^2c)$.Does there exist an algorithm giving at least as accurate results in at least as good time?
What is the current state-of-the-art solver for quadratic knapsack problems?
np hardness;dynamic programming;packing