Research Catalog

Approximation algorithms for NP-hard problems

Title: Approximation algorithms for NP-hard problems / edited by Dorit S. Hochbaum.
Publication: Boston : PWS Pub. Co., [1997], ©1997.

Filter by

Item details
Status	Format	Access	Call Number	Item Location
Request for On-site Use Request Scan Not available - Please for assistance.	Text	Request in advance	T57.7 .A68 1997	Off-site

Additional Authors

Hochbaum, Dorit S.

Description

xxii, 596 pages : illustrations; 24 cm

Subjects

Bibliography (note)

Contents

Introduction / Dorit S. Hochbaum -- 1. Approximation Algorithms in Scheduling / Leslie A. Hall -- 2. Approximation Algorithms for Bin Packing: A Survey / E. G. Coffman, Jr., M. R. Garey and D. S. Johnson -- 3. Approximating Covering and Packing Problems: Set Cover, Vertex Cover, Independent Set, and Related Problems / Dorit S. Hochbaum -- 4. The Primal-Dual Method for Approximation Algorithms and Its Application to Network Design Problems / Michel X. Goemans and David P. Williamson -- 5. Cut Problems and Their Application to Divide-and-Conquer / David B. Shmoys -- 6. Approximation Algorithms for Finding Highly Connected Subgraphs / Samir Khuller -- 7. Algorithms for Finding Low Degree Structures / Balaji Raghavachari -- 8. Approximation Algorithms for Geometric Problems / Marshall Bern and David Eppstein -- 9. Various Notions of Approximations: Good, Better, Best, and More / Dorit S. Hochbaum -- 10. Hardness of Approximations / Sanjeev Arora and Carsten Lund --
11. Randomized Approximation Algorithms in Combinatorial Optimization / Rajeev Motwani, Joseph (Seffi) Naor and Prabhakar Raghavan -- 12. The Markov Chain Monte Carlo Method: An Approach to Approximate Counting and Integration / Mark Jerrum and Alistair Sinclair -- 13. Online Computation / Sandy Irani and Anna R. Karlin.

ISBN

0534949681 (hardcover : acid-free paper)

LCCN

95031849

OCLC

Owning Institutions

Columbia University Libraries