Asymptotic Behaviour of the Quadratic Knapsack Problem
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