Approximation of the Quadratic Knapsack Problem
classification
💻 cs.DS
cs.CCcs.DMmath.CO
keywords
epsilonapproximationknapsackproblemquadraticalgorithmgivenratio
read the original 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})$.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.