The Design of Approximation Algorithms

Monografía académica de referencia escrita por David P. Williamson y David B. Shmoys y publicada por Cambridge University Press en 2011, enfocada en el diseño formal y análisis matemático de algoritmos de aproximación eficientes con garantías teóricas demostrables para problemas de optimización combinatoria NP-hard. La obra está orientada a estudiantes de posgrado, investigadores y profesionales avanzados en ciencias de la computación, investigación operativa y matemática aplicada. Exige una sólida base previa en diseño y análisis de algoritmos, teoría de la complejidad computacional (clases P, NP y reducciones), álgebra lineal, cálculo de probabilidades y familiaridad con demostraciones matemáticas rigurosas.

A diferencia de los textos tradicionales estructurados por problemas aislados, la obra organiza su propuesta en torno a los paradigmas de diseño fundamentales: algoritmos codiciosos (greedy) y búsqueda local, redondeo de datos y programación dinámica, esquemas de aproximación en tiempo polinomial (PTAS y FPTAS), programación lineal (LP) y técnicas de redondeo determinista y aleatorizado, programación semidefinida (SDP), el método primal-dual, y cortes y métricas (embeddings métricos). Con estas herramientas analiza y resuelve problemas emblemáticos como Set Cover, Knapsack, el problema del viajante de comercio métrico (TSP), Maximum Satisfiability (MAX-SAT), el algoritmo de Goemans-Williamson para MAX-CUT, Multicut, Multiway Cut y Facility Location, además de abordar temas avanzados como diseño de redes (buy-at-bulk network design) y técnicas para demostrar la dureza de aproximación (inaproximabilidad) basadas en el teorema PCP y reducciones de brecha.

El libro no propone proyectos de desarrollo de software ni programación guiada en lenguajes específicos, sino que expresa todos los algoritmos mediante pseudocódigo matemático formal y concluye cada capítulo con un conjunto riguroso de ejercicios teóricos y notas bibliográficas. Su gran aporte radica en enseñar a pensar de forma metodológica a través de técnicas transferibles a nuevos problemas de optimización, siendo un texto de cabecera en la teoría de la aproximación moderna. Deja fuera la implementación en código ejecutable, la heurística empírica y la optimización en arquitecturas reales de hardware. Conviene dominar previamente la teoría de la dualidad en programación lineal antes de abordar sus capítulos intermedios y avanzados.