Loading...
Please wait, while we are loading the content...
Similar Documents
Der Algorithmus von Howgrave-Graham und Joux zur Lösung von Rucksackproblemen
| Content Provider | Semantic Scholar |
|---|---|
| Author | Ludwig, Michael |
| Copyright Year | 2012 |
| Abstract | In dieser Diplomarbeit werden Algorithmen fur schwere Rucksackinstanzen (in diesem Fall Subset Sum) behandelt. Eine Instanz heist schwer, wenn sie eine Dichtekennzahl nahe 1 hat. Die behandelten Algorithmen bauen aufeinander auf. Beginnend beim Horowitz-Sahni-Algorithmus wurde zunachst 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 auserdem eine Heuristik, deren Korrektheit ebenso bewiesen wurde. |
| File Format | PDF HTM / HTML |
| DOI | 10.18419/opus-2891 |
| Alternate Webpage(s) | https://elib.uni-stuttgart.de/bitstream/11682/2908/1/DIP_3259.pdf |
| Alternate Webpage(s) | https://doi.org/10.18419/opus-2891 |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |