  


Asymptotic Behaviour of the Quadratic Knapsack Problem
Joachim Schauer(joachim.schauerunigraz.at) Abstract: 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 is not far away from the optimal solution. More specifically we show the the ratio of the optimal solution and the objective value of this heuristic almost surely tends to 1 as the size of the knapsack instance tends to infinity. As a consequence using randomly generated instances following this scheme seems to be inappropriate for studying the performance of heuristics and (to some extend) exact methods. However such instances are frequently used in the literature for this purpose. Additionally we introduce a new class of test instances for which finding a good solution is much harder. We support this by theoretical observations as well as by performing computational experiments. Keywords: quadratic knapsack problem, asymptotic analysis, random instances Category 1: Combinatorial Optimization (Other ) Citation: University of Graz, Department of Statistics and Operations Research, Universitaetsstr. 15, A8010 Graz, Austria Download: [PDF] Entry Submitted: 07/30/2015 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  