Approximation of the Quadratic Knapsack Problem
arXiv:1509.01866
Abstract
For any given $ε>0$ we provide an algorithm for the Quadratic Knapsack Problem that has an approximation ratio within $O(n^{2/5+ε})$ and a run time within $O(n^{9/ε})$.
8 pages one figure