Literatur

• Silvano Martello, Paolo Toth: Knapsack Problems -- Algorithms and Computer Implementations. Wiley, 1990 (LINK)
• Hans Kellerer, Ulrich Pferschy, David Pisinger: Knapsack Problems. Springer, 2004
• Bernhard Korte, Jens Vygen: Combinatorial Optimization -- Theory and Algorithms (Kapitel 17 und 18). Springer, 2007

Themen

• Binäre Rucksackprobleme
  • Fraktionale Rucksackprobleme
    (Moritz Keuthen, Di 19.05.)
  • Obere Schranken
    (Andreas Hauptmann, Di 26.05.)
  • Branch-and-Bound-Algorithmen
    (Thomas Geisinger, Di 09.06.)
  • Pseudopolynomielle Algorithmen
    (Peter Mayer, Di 16.06.)
  • Polynomielle Approximationsschemata
    (Martin Huber, Do 18.06.)
  • Subset-Sum-Probleme
    (Leonhard Schiele, Di 23.06.)

• Ganzzahlige Rucksackprobleme
  • Beschränkte ganzzahlige Rucksackprobleme
    (Alexander Dehlinger, Do 25.06.)
  • Unbeschränkte ganzzahlige Rucksackprobleme
    (Dino Dittrich, Di 30.06.)

• Bin-Packing
  • Greedy-Heuristiken
    (Richard Szöke-Schuller, Do 02.07.)
  • Untere Schranken
    (Sien Lu, Di 07.07.)
  • Asymptotisches Approximationsschema
    (Jingjing Gu, Do 09.07.)