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

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).