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:




Library Locked Library locked




Author, Editor(s)

Author(s):

Beier, René
Vöcking, Berthold

dblp
dblp

Not MPG Author(s):

Berthold Vöcking

BibTeX cite key*:

Beier2004e

Title

Title*:

Random knapsack in expected polynomial time

Journal

Journal Title*:

Journal of Computer and System Sciences

Journal's URL:

http://www.sciencedirect.com/science/journal/00220000

Download URL
for the article:

http://dx.doi.org/10.1016/j.jcss.2004.04.004

Language:

English

Publisher

Publisher's
Name:

Elsevier

Publisher's URL:

http://www.elsevier.com

Publisher's
Address:


ISSN:


Vol, No, pp, Date

Volume*:

69

Number:

3

Publishing Date:

June 2004

Pages*:

306-329

Number of
VG Pages:

25

Page Start:

306

Page End:

329

Sequence Number:


DOI:


Note, Abstract, ©

Note:


(LaTeX) Abstract:

We present the first average-case analysis proving a polynomial upper bound
on the expected running time of an exact algorithm for the 0/1 knapsack problem.
In particular, we prove for various input distributions, that the number of
Pareto-optimal knapsack fillings is polynomially bounded in the number of availa
ble items.
An algorithm by Nemhauser and Ullmann can enumerate these solutions very
efficiently so that a polynomial upper bound on the number of Pareto-optimal sol
utions
implies an algorithm with expected polynomial running time.

The random input model underlying our analysis is quite general
and not restricted to a particular input distribution. We assume adversarial
weights and randomly drawn profits (or vice versa). Our analysis covers general
probability
distributions with finite mean and, in its most general form, can even
handle different probability distributions for the profits of different items.
This feature enables us to study the effects of correlations between profits
and weights. Our analysis confirms and explains practical studies showing
that so-called {\em strongly correlated\/} instances are harder to solve than
{\em weakly correlated\/} ones.

URL for the Abstract:

http://dx.doi.org/10.1016/j.jcss.2004.04.004

Categories,
Keywords:

Knapsack Problem, Exact Algorithms, Average Case Analysis

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{Beier2004e,
AUTHOR = {Beier, Ren{\'e} and V{\"o}cking, Berthold},
TITLE = {Random knapsack in expected polynomial time},
JOURNAL = {Journal of Computer and System Sciences},
PUBLISHER = {Elsevier},
YEAR = {2004},
NUMBER = {3},
VOLUME = {69},
PAGES = {306--329},
MONTH = {June},
}


Entry last modified by Uwe Brahm, 07/08/2014
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)
[Library]
Created
04/12/2006 09:34:28 AM
Revision
1.
0.


Editor
Uwe Brahm
René Beier


Edit Date
08-05-2006 19:25:12
04/12/2006 09:34:28 AM