Le champ des algorithmes d'approximation

est aujourd'hui l'un des domaines de recherche

les plus actifs en informatique. Il allie

la profondeur de la théorie mathématique aux

promesses d'applications pratiques d'un intérêt

considérable.

La plupart des problèmes issus d'applications

relevant de domaines aussi différents que

la conception de circuits VLSI, la conception et

la planification de réseaux, l'ordonnancement,

la théorie des jeux, la biologie ou la théorie

des nombres, sont des problèmes NP-difficiles.

Leur résolution exacte demanderait des

ressources informatiques inaccessibles et ne peut

donc être envisagée. Pour faire face à cette

situation, un grand nombre d'algorithmes

proposant des solutions approchées à

ces problèmes ont été développés. Une quantité

considérable de résultats nouveaux a été établie

lors de la dernière décennie et a révolutionné

ce champ d'étude.

Le défi relevé par cet ouvrage est de présenter

clairement les théories et méthodologies sous-jacentes

sans rien ôter à la beauté des résultats.

Ce livre expose ces questions algorithmiques

complexes en proposant des démonstrations

simples et intuitives accompagnées

de nombreux exemples.