-

 

 

 




Optimization Online





 

Asymptotic Behaviour of the Quadratic Knapsack Problem

Joachim Schauer(joachim.schauer***at***uni-graz.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, A-8010 Graz, Austria

Download: [PDF]

Entry Submitted: 07/30/2015
Entry Accepted: 07/30/2015
Entry Last Modified: 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
Mathematical Optimization Society