Mehrdimensionale Packungsprobleme

Inhaltlich unveränderte Neuauflage. Das Rucksackproblem ist eines der grundlegenden Probleme der Informatik. Die in diesem Buch betrachtete Variante lässt sich leicht anhand einer alltäglichen Situation beschreiben: Wie finde ich eine Auswahl an Gegenständen, die sich gemeinsam in meinen Rucksack packen lassen und mir bei meiner Reise den größtmöglichen Nutzen bringen? In der kombinatorischen Optimierung beschränkt man sich auf rechteckige Gegen­stände und Rucksäcke. Anwendungen finden sich bei Schnittproblemen - hier werden Objekte aus einem Materialblock herausgeschnitten - sowie in der Transportindustrie. Der Autor gibt einführend einen Überblick über die ver­schiedenen Verallgemeinerungen klassischer Packungsprobleme. Dies sind neben dem Rucksackproblem auch das Aufteilungs- sowie ein Stapelungsproblem. Nach einer ausführlichen Behandlung wichtiger Metho­den werden Approximationsalgorithmen für die zweidimensionalen Problem­varianten vorgestellt. Darauf aufbauend werden die höherdimensionalen Probleme behandelt. Das Buch richtet sich an Studenten der Informatik, die ihren Schwerpunkt auf den Bereich Algorithmik legen, sowie an alle, die sich im wissenschaftlichen Kontext mit Approximationsalgorithmen beschäftigen.