Logo der Humboldt-Universität zu BerlinLogo der Humboldt-Universität zu Berlin
edoc-Server
Open-Access-Publikationsserver der Humboldt-Universität
de|en
Banner: Fassade der Humboldt-Universität zu Berlin
Publikation anzeigen 
  • edoc-Server Startseite
  • Schriftenreihen und Sammelbände
  • Fakultäten und Institute der HU
  • Institut für Mathematik
  • Preprints aus dem Institut für Mathematik
  • Publikation anzeigen
  • edoc-Server Startseite
  • Schriftenreihen und Sammelbände
  • Fakultäten und Institute der HU
  • Institut für Mathematik
  • Preprints aus dem Institut für Mathematik
  • Publikation anzeigen
JavaScript is disabled for your browser. Some features of this site may not work without it.
Gesamter edoc-ServerBereiche & SammlungenTitelAutorSchlagwortDiese SammlungTitelAutorSchlagwort
PublizierenEinloggenRegistrierenHilfe
StatistikNutzungsstatistik
Gesamter edoc-ServerBereiche & SammlungenTitelAutorSchlagwortDiese SammlungTitelAutorSchlagwort
PublizierenEinloggenRegistrierenHilfe
StatistikNutzungsstatistik
Publikation anzeigen 
  • edoc-Server Startseite
  • Schriftenreihen und Sammelbände
  • Fakultäten und Institute der HU
  • Institut für Mathematik
  • Preprints aus dem Institut für Mathematik
  • Publikation anzeigen
  • edoc-Server Startseite
  • Schriftenreihen und Sammelbände
  • Fakultäten und Institute der HU
  • Institut für Mathematik
  • Preprints aus dem Institut für Mathematik
  • Publikation anzeigen
2005-11-02Buch DOI: 10.18452/2579
The average behaviour of greedy algorithms for the knapsack problem: Computational experiments
Bank, Bernd
Diubin, Gennady
Korbut, Alexander
Sigal, I.
We describe primal and dual greedy algorithms for the one-dimensional knapsack problem with Boolean variables. A theorem concerning their average behaviour is formulated. It is supposed that all coefficients of the problem are independent random variables uniformly distributed on [0,1], and $b=\lambda n$. The theorem asserts that for $\lambda$ exceeding the "critical" value $1/2 - t/3$ both algorithms have asymptotical tolerance $t$. The main goal of the experiments was clarifying the behaviour of the algorithms for pre-critical value of $\lambda$. A brief characterization of a computer program implementing these methods together with preliminary results of the experiments is given. These results confirm the good behaviour of both methods and suggest some interesting theoretical problems.
Dateien zu dieser Publikation
Thumbnail
6.pdf — PDF — 109.6 Kb
MD5: a26a3460891c9b99b459b785fd07a1ae
Referenzen
Is Part Of Series: Preprints aus dem Institut für Mathematik - 6, Mathematik-Preprints, ISSN:0863-0976
Zitieren
BibTeX
EndNote
RIS
Keine Lizenzangabe
Zur Langanzeige
Impressum Leitlinien Kontakt Datenschutzerklärung
Ein Service der Universitätsbibliothek und des Computer- und Medienservice
© Humboldt-Universität zu Berlin
 
DOI
10.18452/2579
Permanent URL
https://doi.org/10.18452/2579
HTML
<a href="https://doi.org/10.18452/2579">https://doi.org/10.18452/2579</a>