An experimental study of random knapsack problems

The size of the Pareto curve for the bicriteria version of the knapsack problem is polynomial on average. This has been shown for various random input distributions. We experimentally investigate the number of Pareto points for knapsack instances over n elements whose profits and weights are chosen...

Full description

Bibliographic Details
Published in:Algorithmica : an international journal in computer science, Vol. 45, No. 1 (2006), p. 121-136
Main Author: Beier, Rene
Other Involved Persons: Vöcking, Berthold
Format: electronic Article
Language:English
ISSN:1432-0541
Item Description:This research was supported in part by the EU within the 6th Framework Programme under Contract 0019007 (DELIS), by DFG Grant Vo889/2-1, and by a postdoctoral fellowship by the German Academic Exchange Service (DAAD).
Physical Description:Online-Ressource
DOI:10.1007/s00453-005-1193-7
Subjects:
QR Code: Show QR Code