Algorithmics for Hard Problems

Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics

Juraj Hromkovic

558 pages, parution le 18/11/2002 (2^eme édition)

Ajouter à une liste

Indisponible

Résumé

There are several approaches to attack hard problems. All have their merits, but also their limitations, and need a large body of theory as their basis. A number of books for each one exist: books on complexity theory, others on approximation algorithms, heuristic approaches, parametrized complexity, and yet others on randomized algorithms. This book discusses thoroughly all of the above approaches. And, amazingly, at the same time, does this in a style that makes the book accessible not only to theoreticians, but also to the non-specialist, to the student or teacher, and to the programmer. Do you think that mathematical rigor and accessibility contradict? Look at this book to find out that they do not, due to the admirable talent of the author to present his material in a clear and concise way, with the idea behind the approach spelled out explicitly, often with a revealing example.

Reading this book is a beautiful experience and I can highly recommend it to anyone interested in learning how to solve hard problems. It is not just a condensed union of material from other books. Because it discusses the different approaches in depth, it has the chance to compare them in detail, and, most importantly, to highlight under what circumstances which approach might be worth exploring. No book on a single type of solution can do that, but this book does it in an absolutely fascinating way that can serve as a pattern for theory textbooks with a high level of generality.(Peter Widmayer)

The second edition extends the part on the method of relaxation to linear programming with an emphasis on rounding, LP-duality, and primal-dual schema, and provides a self-contained and transparent presentation of the design of randomized algorithms for primality testing.

Contents

1- Introduction

2- Elementary Fundamentals

Introduction
Fundamentals of Mathematicals
Fundamentals of Algorithms

3- Deterministic Approaches

Introduction
Pseudo-Polynomial-Time Algorithms
Parameterized Complexity
Branch-and-Bound
Lowering Worst Case Complexity of Exponential Algorithms
Local Search
Relaxation to Linear Programming
Bibliographical Remarks

4- Approximation Algorithms

Introduction
Fundamentals
Algorithm Design
Inapproximability
Bibliographical Remarks

5- Randomized Algorithms Introduction

Classification and Randomized Algorithms and Design Paradigms
Design of Randomized Algorithms
Derandomization
Bibliographical Remarks

6- Heuristics

Introduction
Simulated Annealing
Genetic Algorithms
Bibliographical Remarks

7- A Guide to Solving Hard Problems

Introduction
Taking over an Algorithm Task or a few Words about Money
Combining Different Concepts and Techniques
Comparing Different Approaches
Speedup by Parallelization
New Technologies
Glossary of Basic Terms

Caractéristiques techniques

	PAPIER
Éditeur(s)	Springer
Auteur(s)	Juraj Hromkovic
Parution	18/11/2002
Édition	2^eme édition
Nb. de pages	558
Format	16 x 24
Couverture	Relié
Poids	946g
Intérieur	Noir et Blanc
EAN13	9783540441342