# What is the current “state-of-the-art” solver for quadratic knapsack problems?

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?

• This problem generalizes densest k-subgraph, so the best known provable approximation guarantees are no better than $n^{1/4}$. – Sasho Nikolov Jul 25 '15 at 2:23
• Your question seems fine. You can also consult the help center for what types of questions are appropriate, but you seem to have grasped the essentials on your own. – chazisop Jul 25 '15 at 12:56