MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Beier, Rene
Vöcking, Berthold
dblp
dblp
Editor(s):
BibTeX cite key*:
Beier2003
Title, Booktitle
Title*:
Random Knapsack in Expected Polynomial Time
Booktitle*:
Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC-03)
Event, URLs
Conference URL::
http://www.egr.unlv.edu/~bein/stoc03.html
Downloading URL:
Event Address*:
San Diego, USA
Language:
English
Event Date*
(no longer used):
June, 9-11
Organization:
Association of Computing Machinery (ACM)
Event Start Date:
16 January 2004
Event End Date:
16 January 2004
Publisher
Name*:
ACM
URL:
Address*:
New York, USA
Type:
Vol, No, Year, pp.
Series:
Volume:
Number:
Month:
Pages:
232-241
Year*:
2003
VG Wort Pages:
33
ISBN/ISSN:
1-58113-674-9
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
In this paper, we present the first average-case analysis proving an expected
polynomial running time for an exact algorithm for the 0/1 knapsack problem.
In particular, we prove, for various input distributions, that the number of
{\em dominating solutions\/} (i.e., Pareto-optimal knapsack fillings)
to this problem is polynomially bounded in the number of available items.
An algorithm by Nemhauser and Ullmann can enumerate these solutions very
efficiently so that a polynomial upper bound on the number of dominating solutions
implies an algorithm with expected polynomial running time.

The random input model underlying our analysis is very 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.
Keywords:
Knapsack problem, Exact algorithm, Average Case Analysis
Download
Access Level:
Public

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:

@INPROCEEDINGS{Beier2003,
AUTHOR = {Beier, Rene and V{\"o}cking, Berthold},
TITLE = {Random Knapsack in Expected Polynomial Time},
BOOKTITLE = {Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC-03)},
PUBLISHER = {ACM},
YEAR = {2003},
ORGANIZATION = {Association of Computing Machinery (ACM)},
PAGES = {232--241},
ADDRESS = {San Diego, USA},
ISBN = {1-58113-674-9},
}


Entry last modified by Sabine Krott, 06/17/2004
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)
Rene Beier
Created
05/07/2003 01:46:13 PM
Revisions
6.
5.
4.
3.
2.
Editor(s)
Sabine Krott
Sabine Krott
Christine Kiesel
Christine Kiesel
Christine Kiesel
Edit Dates
17.06.2004 10:41:38
17.06.2004 10:40:50
15.06.2004 15:18:00
11.06.2004 17:09:06
01/16/2004 03:41:27 PM