We study subclasses of the quadratic knapsack problem, where the profits are independent random variables defined on the interval [0,1] and the knapsack capacity is proportional to the number of items (we assume that the weights are arbitrary numbers from the interval [0,1]). We show asymptotically that the objective value of a very easy heuristic … Read more
We study the approximability of the classical quadratic knapsack problem (QKP) on special graph classes. In this case the quadratic terms of the objective function are not given for each pair of knapsack items. Instead an edge weighted graph G = (V,E) whose vertices represent the knapsack items induces a quadratic profit p_ij for the … Read more
The Quadratic Knapsack Problem can be formulated, using an idea of Glover, as a mixed 0-1 linear program with only 2n variables. We present a simple method for strengthening that formulation, which gives good results when the profit matrix is dense and non-negative. Citation Working Paper, Department of Management Science, Lancaster University, May 2007. Article … Read more