Approximation algorithms for NP-hard problems

Approximation algorithm for scheduling / Leslie A. Hall -- Approximation algorithms for bin packing : a survey / E.G. Coffmann, Jr., M.R. Garey, and D.S. Johnson -- Approximating covering and packing problems : set cover, vertex cover, independent set, and related problems / Dorit S. Hochbaum -- The primal-dual method for approximation algorithms and its application to network design problems / Michel X. Goemans and David P. Williamson -- Cut problems and their application to divide-and-conquer / David B. Shmoys -- Approximation algorithms for finding highly connected subgraphs / Samir Khuller -- Algorithms for finding low degree structures / Balaji Raghavachari -- Approximation algorithms for geometric problems / Marshall Bern and David Eppstein -- Various notions of approximations : good, better, best, and more / Dorit S. Hochbaum -- Hardness of approximations / Sanjeev Arora and Carsten Lund -- Randomized approximation algorithms in combinatorial optimization / Rajeev Motwani, Joseph (Seffi) Naor, and Prabhakar Raghavan -- The Markov chain Monte Carlo method : an approach to approximate counting and integration / Mark Jerrum and Alistair Sinclair -- Online computation / Sandy Irani and Anna R. Karlin This is the first book to fully address the study of approximation algorithms as a tool for coping with intractable problems. With chapters contributed by leading researchers in the field, this book introduces unifying techniques in the analysis of approximation algorithms. APPROXIMATION ALGORITHMS FOR NP-HARD PROBLEMS is intended for computer scientists and operations researchers interested in specific algorithm implementations, as well as design tools for algorithms. Among the techniques discussed: the use of linear programming, primal-dual techniques in worst-case analysis, semidefinite programming, computational geometry techniques, randomized algorithms, average-case analysis, probabilistically checkable proofs and inapproximability, and the Markov Chain Monte Carlo method. The text includes a variety of pedagogical features: definitions, exercises, open problems, glossary of problems, index, and notes on how best to use the book. Discussing approximation algorithms for n-p hard problems, this study details scheduling, connectivity problems, randomization in approximations, best possible results, and on-line and server problems.