Approximation of the Quadratic Knapsack Problem

Abstract

For any given $\epsilon >0$ we provide an algorithm for the Quadratic Knapsack Problem that has an approximation ratio within $O(n^{2/5+\epsilon })$ and a run time within $O(n^{9/\epsilon })$.

arXiv comment8 pages one figure