PRODUKTBESCHREIBUNG
von Vijay V. Vazirani (Autor)
Obwohl dies wie ein Paradoxon erscheinen mag, wird jede exakte Wissenschaft von der Idee der Annäherung beherrscht. Bertrand Russell (1872-1970) Die meisten natürlichen Optimierungsprobleme, einschließlich derer, die in wichtigen Anwendungsbereichen auftreten, sind NP-schwer. Daher ist ihre exakte Lösung unter der weit verbreiteten Annahme, dass P -=/= NP, prohibitiv zeitaufwendig. Das Abbilden der Approximationslandschaft dieser Probleme mittels polynomialer Algorithmen wird daher zu einem zwingenden Gegenstand wissenschaftlicher Untersuchung in der Informatik und Mathematik. Dieses Buch präsentiert die Theorie der Approximationsalgorithmen, wie sie heute existiert. Es ist vernünftig anzunehmen, dass sich das Bild mit der Zeit ändern wird. Dieses Buch ist in drei Teile gegliedert. In Teil I behandeln wir kombinatorische Algorithmen für eine Reihe wichtiger Probleme unter Verwendung einer Vielzahl von Algorithmusentwurfstechniken. Letzteres könnte Teil I ein inkohärentes Erscheinungsbild verleihen. Dies ist jedoch zu erwarten – die Natur ist sehr reich, und wir können nicht erwarten, dass ein paar Tricks helfen, die vielfältige Sammlung NP-schwerer Probleme zu lösen. Tatsächlich haben wir in diesem Teil bewusst darauf verzichtet, algorithmische Techniken eng zu kategorisieren, um die Angelegenheiten nicht zu trivialisieren. Stattdessen haben wir versucht, den individuellen Charakter jedes Problems so genau wie möglich zu erfassen und Verbindungen zwischen Problemen und Algorithmen zu deren Lösung aufzuzeigen.
Rückseite
Dieses Buch behandelt die dominierenden theoretischen Ansätze zur approximativen Lösung schwerer kombinatorischer Optimierungs- und Aufzählungsprobleme. Es enthält elegante kombinatorische Theorie, nützliche und interessante Algorithmen sowie tiefe Ergebnisse über die intrinsische Komplexität kombinatorischer Probleme. Seine Klarheit der Darstellung und die exzellente Auswahl an Übungen werden es allen zugänglich und ansprechend machen, die eine Vorliebe für Mathematik und Algorithmen haben.
Richard Karp, Universitätsprofessor, University of California at Berkeley
Nach der Entwicklung grundlegender kombinatorischer Optimierungstechniken in den 1960er und 1970er Jahren war eine der wichtigsten offenen Fragen die Entwicklung einer Theorie der Approximationsalgorithmen. In den 1990er Jahren führten parallele Entwicklungen bei Techniken zur Entwicklung von Approximationsalgorithmen sowie Methoden zum Nachweis der Schwierigkeit von Approximationsergebnissen zu einer wunderschönen Theorie. Die Notwendigkeit, wirklich große Instanzen von rechnerisch schwierigen Problemen zu lösen, wie sie beispielsweise aus dem Internet oder dem Humangenomprojekt stammen, hat das Interesse an dieser Theorie ebenfalls erhöht. Das Feld ist derzeit sehr aktiv, wobei das Werkzeugkästchen der Approximationsalgorithmen-Designtechniken immer reicher wird.
Es ist mir eine Freude, Vijay Vaziranis gut geschriebenes und umfassendes Buch zu diesem wichtigen und aktuellen Thema zu empfehlen. Ich bin sicher, der Leser wird es sowohl als Einführung in die Approximierbarkeit als auch als Referenz zu den vielen Aspekten der Approximationsalgorithmen äußerst nützlich finden.
László Lovász, Senior Researcher, Microsoft Research
