Journal Article @Article Artikel in Fachzeitschrift
 Show entries of: this year (2019) | last year (2018) | two years ago (2017) | Notes URL
 Action: login to update Options: Goto entry point

 Author, Editor(s)
 Author(s): Beier, René Vöcking, Berthold dblp dblp Not MPG Author(s): Vöcking, Berthold
 BibTeX cite key*: Beier2006b

 Title
 Title*: An Experimental Study of Random Knapsack Problems

 Journal

 Publisher
 Publisher's Name: Springer Publisher's URL: http://www.springer-ny.com/ Publisher's Address: New York, USA ISSN: 0178-4617

 Vol, No, pp, Date
 Volume*: 45 Number: 1 Publishing Date: February 2006 Pages*: 121-136 Number of VG Pages: 15 Page Start: 121 Page End: 136 Sequence Number: DOI:

 Note: (LaTeX) Abstract: 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 at random according to various classes of input distributions. The numbers observed in our experiments are significantly smaller than the known upper bounds. For example, the upper bound for so-called uniform instances is $O(n^3)$. Based on our experiments, we conjecture that the number of Pareto points for these instances is only $\Theta(n^2)$. We also study other structural properties for random knapsack instances that have been used in theoretical studies to bound the average-case complexity of the knapsack problem. Furthermore, we study advanced algorithmic techniques for the knapsack problem. In particular, we review several ideas that originate from theory as well as from practice. Most of the concepts that we use are simple and have been known since at least 20 years, but apparently have not been used in this combination. Surprisingly, the result of our study is a very competitive code that outperforms the best previous implementation \emph{Combo} by orders of magnitude for various classes of random instances, including harder random knapsack instances in which profits and weights are chosen in a correlated fashion. URL for the Abstract: http://www.springerlink.com/content/q466425k21257m12/ Categories, Keywords: Knapsack problem - Random instances - Experimental study - Pareto optimality HyperLinks / References / URLs: Copyright Message: Personal Comments: Download Access Level: Intranet

 Correlation
 MPG Unit: Max-Planck-Institut für Informatik MPG Subunit: Algorithms and Complexity Group Appearance: MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:

@ARTICLE{Beier2006b,
AUTHOR = {Beier, Ren{\'e} and V{\"o}cking, Berthold},
TITLE = {An Experimental Study of Random Knapsack Problems},
JOURNAL = {Algorithmica},
PUBLISHER = {Springer},
YEAR = {2006},
NUMBER = {1},
VOLUME = {45},
PAGES = {121--136},