<p>New to this forum, so please let me know if my question format is incorrect.</p>

<p>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 <a href="http://www.optimization-online.org/DB_FILE/2012/03/3392.pdf" rel="noreferrer">link</a> giving a lower bound within 0.05% of true solutions in $\mathcal{O}(n^2c)$.</p>

<p>Does there exist an algorithm giving at least as accurate results in at least as good time?</p>

CC BY-SA 3.0
2015-07-25T02:23:48.913Z
This problem generalizes densest k-subgraph, so the best known *provable* approximation guarantees are no better than $n^{1/4}$.
Sasho Nikolov
CC BY-SA 3.0
2015-07-25T12:56:40.167Z
Your question seems fine. You can also consult the [help center](http://cstheory.stackexchange.com/help) for what types of questions are appropriate, but you seem to have grasped the essentials on your own.
chazisop
<np-hardness><dynamic-programming><packing>
What is the current "state-of-the-art" solver for quadratic knapsack problems?
maybe
# What is the current "state-of-the-art" solver for quadratic knapsack problems?

(Asked by: username_0 on 2015-07-24)

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](http://www.optimization-online.org/DB_FILE/2012/03/3392.pdf) 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?

**Tags:** np-hardness, dynamic-programming, packing
> **Comments:**
> **username_1**: This problem generalizes densest k-subgraph, so the best known *provable* approximation guarantees are no better than $n^{1/4}$.  
> **username_2**: Your question seems fine. You can also consult the [help center](http://cstheory.stackexchange.com/help) for what types of questions are appropriate, but you seem to have grasped the essentials on your own.  

---

## 0 answers

