Descripción

Ejemplar nuevo. With chapters contributed by leading researchers in the field, this book provides computer scientists and operations researchers with an effective framework for analyzing approximation algorithms and applying them to the solution of intractable problems. Each chapter examines a specific problems, low-degree structures, Euclidian problems, multicommodity problems, covering and packing problems and explores unifying problem-solving techniques. These techniques include the use of linear programming, computational geometry techniques, randomized algorithms, average-case analysis, probabilistically checkable proofs and inapproximability, and the Markov Chain Monte Carlo method. The book features a variety of aids to learning and application, including definitions, exercises, open-ended problems, a glossary of problems, an index, and notes on how best to use the book to derive solutions with guaranteed approximability