DESIGN OF APPROXIMATION ALGORITHMS

This is the companion website for the book The Design of Approximation Algorithms by David P. Williamson and David B. Shmoys, published by Cambridge University Press... Interesting discrete optimization problems are everywhere, from traditional operations research planning problems, such as scheduling, facility location, and network design, to computer science problems in databases, to advertising issues in viral marketing. Yet most interesting discrete optimization problems are NP-hard. Thus unless P = NP, there are no efficient algorithms to find optimal solutions to such problems. This book shows how to design approximation algorithms: efficient algorithms that find provably near-optimal solutions.