Approximative Algorithmen und Nichtapproximierbarkeit / / Klaus Jansen, Marian Margraf.

• Superior document: Title is part of eBook package: De Gruyter DGBA Mathematics - 2000 - 2014
• VerfasserIn: Jansen, Klaus,; Margraf, Marian,
• Place / Publishing House: Berlin ;, Boston : : De Gruyter, , [2008]; ©2008
• Year of Publication: 2008
• Language: German
• Series: De Gruyter Lehrbuch
• Physical Description: 1 online resource
• Other title: Frontmatter --; Inhaltsverzeichnis --; Kapitel 1 Einführung --; Kapitel 2 Die Komplexitätsklassen P und NP --; Kapitel 3 Approximative Algorithmen mit additiver --; Güte --; Kapitel 4 Algorithmen mit multiplikativer Güte I: --; Zwei Beispiele --; Kapitel 5 Algorithmen mit multiplikativer Güte II: --; Graphenprobleme --; Kapitel 6 Algorithmen mit multiplikativer Güte III: --; Prozessoptimierung --; Kapitel 7 Algorithmen mit multiplikativer Güte IV: --; Packungsprobleme --; Kapitel 8 Approximationsschemata --; Kapitel 9 Vollständige --; Approximationsschemata --; Kapitel 10 Randomisierte Algorithmen --; Kapitel 11 Lineare Programmierung: --; Deterministisches und randomisiertes Runden --; Kapitel 12 Lineare Programmierung und --; Dualität --; Kapitel 13 Asymptotische polynomielle --; Kapitel 14 MIN JOB SCHEDULING --; Kapitel 15 Max-Min Resource Sharing --; Kapitel 16 Semidefinite Programmierung --; Kapitel 17 Komplexitätstheorie für --; Optimierungsprobleme --; Kapitel 18 Nichtapproximierbarkeit I --; Kapitel 19 PCP Beweissysteme --; Kapitel 20 Nichtapproximierbarkeit II --; Backmatter
• Format: Mode of access: Internet via World Wide Web.
• ISBN: 9783110203172; 9783110637205; 9783110212129; 9783110209082
• DOI: 10.1515/9783110203172
• Access: restricted access
• Hierarchical level: Monograph
• Statement of Responsibility: Klaus Jansen, Marian Margraf.

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.