Algoritmos de Aproximación- Vijay V. Vazirani

Aunque esto pueda parecer una paradoja, toda la ciencia exacta está dominada por la idea de aproximación. Bertrand Russell (1872-1970) La mayoría de los problemas naturales de optimización, incluyendo los que surgen en áreas de aplicación importantes, son NP-hard. Por lo tanto, bajo la creencia ampliamente creída de que P - = / = NP, su solución exacta es prohibitivamente consume tiempo. El trazado del paisaje de aproximación de estos problemas, a través de algoritmos de tiempo polinomial, se convierte así en un tema convincente de la investigación científica en informática y matemáticas. Este libro presenta la teoría de los algoritmos de aproximación AP tal como está hoy. Es razonable esperar que la imagen cambie con el tiempo. Este libro está dividido en tres partes. En la Parte I cubrimos los algoritmos combinatorios para una serie de problemas importantes, utilizando una amplia variedad de técnicas de diseño de algoritmos. Este último puede dar a la Parte I una apariencia no cohesiva. Sin embargo, esto es de esperar - la naturaleza es muy rica, y no podemos esperar algunos trucos para ayudar a resolver la diversa colección de problemas NP-duro. De hecho, en esta parte, nos hemos abstenido deliberadamente de agrupar las técnicas algorítmicas para no trivializar las cosas. En cambio, hemos tratado de captar lo más exactamente posible el carácter individual de cada problema y señalar las conexiones entre los problemas y los algoritmos para resolverlos.