Approximation algorithms for NP-hard problems / edited by Dorit S. Hochbaum.
Contributor(s): Hochbaum, Dorit S
.
Material type: 
BookPublisher: Boston : PWS Pub. Co., c1997Description: xxii, 596 p. : ill. ; 24 cm. +\ehbk.ISBN: 0534949681.Subject(s): Programming (Mathematics) | Approximation theory | AlgorithmsDDC classification: 511.42 | Item type | Current library | Call number | Copy number | Status | Date due | Barcode | Item holds |
|---|---|---|---|---|---|---|---|
| General Lending | MTU Bishopstown Library Lending | 511.42 (Browse shelf(Opens below)) | 1 | Available | 00015044 |
Enhanced descriptions from Syndetics:
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.
Includes bibliographical references and index.
Introduction / Dorit S Hochbaum -- Approximation algorithms for scheduling / Leslie A. Hall -- Approximation, algorithms for bin packing; a survey / E. G. Coffman, 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 notations of approximations: good, better, best and more / Dorit S. Hochbaum -- Hardness of approximations / Sanjeev Anora and Carsten Land -- 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.
Table of contents provided by Syndetics
- Introduction
- 1 Approximation Algorithms for Scheduling
- 2 Approximation Algorithms for Bin Packing: a Survey
- 3 Approximating Covering and Packing Problems: Set Cover, Vertex Cover, Independent Set, and Related Problems
- 4 The Primal-Dual Method for Approximation Algorithms and its Application to Network Design Problems
- 5 Cut Problems and Their Application to Divide-and-Conquer
- 6 Approximation Algorithms for Finding Highly Connected Subgraphs
- 7 Algorithms for Finding Low Degree Structures
- 8 Approximation Algorithms for Geometric Problems
- 9 Various Notions of Approximations: Good, Better, Best, and More
- 10 Hardness of Approximations
- 11 Randomized Approximation Algorithms in Combinatorial Optimization
- 12 The Markov Chain Monte Carlo Method: An Approach to Approximate Counting and Integration
- 13 Online Computation