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?

  • 3
    $\begingroup$ This problem generalizes densest k-subgraph, so the best known provable approximation guarantees are no better than $n^{1/4}$. $\endgroup$ – Sasho Nikolov Jul 25 '15 at 2:23
  • $\begingroup$ 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. $\endgroup$ – chazisop Jul 25 '15 at 12:56

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.