Approximative Algorithmen und Nichtapproximierbarkeit

Gegenstand dieses Lehrbuchs ist die Behandlung schwer lösbarer diskreter Optimierungsprobleme. Im ersten Teil werden schnelle Algorithmen vorgestellt, die solche Probleme näherungsweise lösen können. Der zweite Teil behandelt Komplexitätstheorie und Nichtapproximierbarkeit von Optimierungsproblemen. Das Lehrbuch enthält zudem zahlreiche Anwendungsbeispiele, Übungsaufgaben, Illustrationen und Abschnitte über Grundlagen wie etwa die Turingmaschine.

Autorentext

Klaus Jansen und Marian Markgraf, Universität Kiel.

Klappentext

The subject matter of this textbook is the treatment of difficult to solve discrete optimisation problems. The first part presents fast algorithms which can provide approximate solutions to such problems. The second part deals with complexity theory and the non-approximability of optimisation problems. In addition, this textbook contains numerous application examples, exercises, illustrations and sections on the basics such as the Turing machine.