Diplomarbeit DIP-2012-26

Bibliograph.
Daten
Ludwig, Michael: Der Algorithmus von Howgrave-Graham und Joux zur Lösung von Rucksackproblemen.
Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik, Diplomarbeit Nr. 26 (2012).
67 Seiten, deutsch.
Kurzfassung

In dieser Diplomarbeit werden Algorithmen für schwere Rucksackinstanzen (in diesem Fall Subset Sum) behandelt. Eine Instanz heißt schwer, wenn sie eine Dichtekennzahl nahe 1 hat. Die behandelten Algorithmen bauen aufeinander auf. Beginnend beim Horowitz-Sahni-Algorithmus wurde zunächst der Schroeppel-Shamir-Algorithmus und danach der Algorithmus von Howgrave-Graham und Joux hergeleitet. Letzterer hat einen Speicher-Zeit-Tradeoff, welcher in dieser Arbeit ausgebaut werden konnte. Die neuen Algorithmen verwenden außerdem eine Heuristik, deren Korrektheit ebenso bewiesen wurde.

Volltext und
andere Links
Volltext
Abteilung(en)Universität Stuttgart, Institut für Formale Methoden der Informatik, Formale Konzepte
BetreuerDiekert, Prof. Volker
Eingabedatum4. November 2019
   Publ. Institut   Publ. Informatik