Algorithmics for Hard Problems: Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics

✍ Scribed by Juraj Hromkovič

• Publisher: Springer
• Year: 2001
• Tongue: English
• Leaves: 500
• Series: Texts in Theoretical Computer Science. An EATCS Series
• Edition: 1st
• Category: Library

✦ Synopsis

This textbook provides a "cheap ticket" to the design of algorithms for hard
computing problems, Le., for problems for which no low-degree polynomial-time
algorithms1 are known. It focuses on a systematic presentation of the fundamental
concepts and algorithm design techniques. The
presentation of these concepts and techniques starts with some fundamental
informal ideas that are later consecutively specified in detail. The algorithms
used to illustrate the application of these methods are chosen with respect to
their simplicity and transparency rather than with respect to their quality (complexity
and reliability).

✦ Table of Contents

Front Matter....Pages I-XI
Introduction....Pages 1-9
Elementary Fundamentals....Pages 11-142
Deterministic Approaches....Pages 143-212
Approximation Algorithms....Pages 213-305
Randomized Algorithms....Pages 307-385
Heuristics....Pages 387-415
A Guide to Solving Hard Problems....Pages 417-457
Back Matter....Pages 459-494

✦ Subjects

Discrete Mathematics in Computer Science;Algorithm Analysis and Problem Complexity;Artificial Intelligence (incl. Robotics);Computational Mathematics and Numerical Analysis;Combinatorics;Complexity