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:








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

Journal Title*:

Algorithmica

Journal's URL:

http://www.springerlink.com/content/1432-0541/

Download URL
for the article:

http://www.springerlink.com/content/q466425k21257m12/fulltext.pdf

Language:

English

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, Abstract, ©

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},
ADDRESS = {New York, USA},
MONTH = {February},
ISBN = {0178-4617},
}


Entry last modified by Christine Kiesel, 02/05/2007
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
René Beier
Created
12/13/2006 10:54:08 AM
Revisions
4.
3.
2.
1.
0.
Editor(s)
Christine Kiesel
Christine Kiesel
René Beier
René Beier
René Beier
Edit Dates
05.02.2007 17:16:35
05.02.2007 17:16:00
01/22/2007 03:03:41 PM
01/18/2007 11:22:41 AM
12/13/2006 10:54:08 AM