Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

Probabilistic Analysis of Knapsack Core Algorithms

MPG-Autoren
/persons/resource/persons44108

Beier,  Rene
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45673

Vöcking,  Berthold
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine externen Ressourcen hinterlegt
Volltexte (beschränkter Zugriff)
Für Ihren IP-Bereich sind aktuell keine Volltexte freigegeben.
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte in PuRe verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Beier, R., & Vöcking, B. (2004). Probabilistic Analysis of Knapsack Core Algorithms. In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-04) (pp. 461-470). New York, USA: ACM.


Zitierlink: https://hdl.handle.net/11858/00-001M-0000-000F-2918-E
Zusammenfassung
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.