Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor

Author(s):

Beier, Rene
Vöcking, Berthold

dblp
dblp

Not MPG Author(s):

Berthold, Vöcking

Editor(s):





BibTeX cite key*:

Beier2004a

Title, Booktitle

Title*:

Probabilistic Analysis of Knapsack Core Algorithms

Booktitle*:

Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-04)

Event, URLs

URL of the conference:

http://www.siam.org/meetings/da04/

URL for downloading the paper:

http://www.mpi-sb.mpg.de/%7Erbeier/soda04_1.ps.gz

Event Address*:

New Orleans, USA

Language:

English

Event Date*
(no longer used):

January, 11-13

Organization:

Association of Computing Machinery (ACM) and SIAM

Event Start Date:

11 January 2004

Event End Date:

13 January 2004

Publisher

Name*:

ACM

URL:


Address*:

New York, USA

Type:


Vol, No, Year, pp.

Series:


Volume:


Number:


Month:


Pages:

461-470

Year*:

2004

VG Wort Pages:

33

ISBN/ISSN:

0-89871-558-X

Sequence Number:


DOI:




Note, Abstract, ©


(LaTeX) Abstract:

We study the average-case performance of algorithms for the binary knapsack problem.
Our focus lies on the analysis of so-called {\em core algorithms}, the predominant
algorithmic concept used in practice.
These algorithms start with the computation of an optimal fractional solution
that has only one fractional item and then they exchange items until an optimal
integral solution is found.
The idea is that in many cases the optimal integral solution should be close to the fractional
one such that only a few items need to be exchanged.
Despite the well known hardness of the knapsack problem on worst-case instances,
practical studies show that knapsack core algorithms can solve large scale
instances very efficiently.
For example, they exhibit almost linear running time on purely random inputs.

In this paper, we present the first theoretical result on the running time of
core algorithms that comes close to the results observed in practical experiments.
We prove an upper bound of
$O(n \, \polylog(n))$ on the expected running time of a core algorithm on
instances with $n$ items whose profits and weights are drawn independently,
uniformly at random.
A previous analysis on the average-case complexity of the knapsack problem proves
a running time of $O(n^4)$, but for a different kind of algorithms.
The previously best known upper bound on the running time of core
algorithms is polynomial as well. The degree of this polynomial, however, is
at least a large three digit number. In addition to uniformly random instances, we
investigate harder instances in which profits and weights are pairwise correlated.
For this kind of instances, we can prove a tradeoff describing how the degree of
correlation influences the running time.

Keywords:

Theory, 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{Beier2004a,
AUTHOR = {Beier, Rene and V{\"o}cking, Berthold},
TITLE = {Probabilistic Analysis of {Knapsack} Core Algorithms},
BOOKTITLE = {Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-04)},
PUBLISHER = {ACM},
YEAR = {2004},
ORGANIZATION = {Association of Computing Machinery (ACM) and SIAM},
PAGES = {461--470},
ADDRESS = {New Orleans, USA},
ISBN = {0-89871-558-X},
}


Entry last modified by Christine Kiesel, 06/17/2005
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)
Rene Beier
Created
01/16/2004 03:10:02 PM
Revisions
7.
6.
5.
4.
3.
Editor(s)
Christine Kiesel
Christine Kiesel
Christine Kiesel
Christine Kiesel
Christine Kiesel
Edit Dates
17.06.2005 15:39:19
17.06.2005 15:38:24
23.05.2005 14:16:37
23.05.2005 14:08:31
02.02.2005 12:06:29
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section