Algorithmes d’approximation

Vijay V. Vazirani9782287006777, 228700677X

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.