The Design of Approximation Algorithms

Livro digital

Título:
The Design of Approximation Algorithms

Autor:
David P. Williamson, David B. Shmoys

Categoria:
Tecnologia > Geral

Doador:
Raffaello D. N.

Sinopse:
This textbook opens with a very specific promise: it organizes approximation algorithms around design principles, starting from set cover and then building outward through the techniques in the table of contents. The reader is immediately placed in a graduate-level setting, with the book assuming prior algorithms knowledge, probability, and NP-completeness basics. From there, the structure reveals the real range of the material. The first part is built around single algorithmic ideas, including greedy methods, local search, rounding, primal-dual reasoning, and randomized rounding, each applied across several optimization problems. The second part returns to those same ideas in more advanced form, revisiting facility location, prize-collecting Steiner tree, bin packing, and maximum cut, while also emphasizing linear and integer programming as central tools. The result is a rigorous, classroom-tested reference for readers who want both a graduate textbook and a guide into current research. Its value lies in the way it turns approximation algorithms into a coherent design discipline, showing how a handful of techniques can be adapted across many hard optimization problems with practical and theoretical depth.