## Algorithmics for Hard Problems: Introduction to Combinatorial Optimization, Randomization, Approximation, and HeuristicsThis book is an introduction to the methods of designing algorithms for hard computing tasks. This area has developed very dynamically in the last years and is one of the kernels of current research in algorithm and complexity theory. The book mainly concentrates on approximate, randomized and heuristic algorithms, and on the theoretical and experimental comparison of these approaches according to the requirements of the practice. There exist several monographs specializing in some of these methods, but no book systematically explains and compares all main possibilities of attacking hard computing problems. Since the topic is fundamental for the university study in computer science and essential for the transfer of formal methods to the practice, the aim of the book is to close this gap by providing at once a textbook for graduate students and a handbook for practitioners dealing with hard computing problems. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

Introduction | 1 |

Elementary Fundamentals | 11 |

Deterministic Approaches | 143 |

Copyright | |

6 other sections not shown

### Common terms and phrases

A-TSP algorithm design techniques approach approximation algorithms approximation ratio assignment backtracking Boolean function branch-and-bound branching program clauses complexity concept consider constraints contains cost cost(T cover problem decision problem define Definition derandomization deterministic algorithm DNA computing edges efficient Exercise exists exponential feasible solution formula fundamental genetic algorithms given graph G greedy Hamiltonian cycle Hamiltonian tour hard problems input instance knapsack problem Lemma linear equations linear programming lower bounds matrix Max-Sat method minimal Monte Carlo algorithm multigraph neighborhood NP-hard observe Obviously optimal solution optimization problems output parameter parameterized polynomial polynomial-time algorithm polynomial-time approximation polytope positive integer presented prime Prob probability space problem instances proof prove pseudo-polynomial-time algorithms PTAS quadratic nonresidue quantum computation random choice random variable randomized algorithm randomly reduction rithm search algorithm Section sequence simulated annealing solving Step subinstances tabu search Theorem values vector vertex cover vertex cover problem vertices