Approximation Algorithms for NP-hard Problems
- ISBN-10
- 0534949681
- ISBN-13
- 9780534949686
- Category
- Mathematics / Algebra / General
- Pages
- 596
- Language
- English
- Published
- 1997
- Publisher
- PWS Publishing Company
- Author
- Dorit S. Hochbaum
Description
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.
Get the book
Similar books
-
Operator Algebras and Mathematical Physics: Proceedings of a Summer Conference Held June 17-21, 1985 with Support from the National Science...
By Palle E. T. Jørgensen, Paul S. MuhlyOperator Algebras and Mathematical Physics: Proceedings of a Summer Conference Held June 17-21, 1985 with Support from the National Science...
-
A First Course in Abstract Algebra
By John B. FraleighConsidered a classic by many, A First Course in Abstract Algebra, Seventh Edition is an in-depth introduction to abstract algebra. Focused on groups, rings and fields, this...
-
Algebra for College Students
By Margaret L. Lial, E. John Hornsby, Terry McGinnisThe Lial series has helped thousands of readers succeed in developmental mathematics through its approachable writing style, relevant real-world examples, extensive exercise sets, and complete supplements package Review...
-
The Art of Computer Programming: Seminumerical algorithms
By Donald Ervin KnuthV.1 - Fundamentals algorithms: Basic concepts. Algorithms. Mathematical preliminaries. MIX. Some fundamental programming techniques. Information structures. Linear lists. Trees. Multilinked structures. Dynamic storage allocation. History and bibliography. Random numbers. Generating...
-
Orthogonal Polynomials: Estimates, Asymptotic Formulas, and Series of Polynomials Orthogonal on the Unit Circle and on an Interval
By I︠A︡. L. GeronimusOrthogonal Polynomials: Estimates, Asymptotic Formulas, and Series of Polynomials Orthogonal on the Unit Circle and on an Interval
-
Intermediate Algebra
By George WoodburyGeorge Woodbury's Algebra Series empowers students for future success in college-level math courses through its early-and-often approach to functions and graphing, integrated study strategies, and quality exercise sets that...
-
Glencoe Algebra 1, Student Edition
By McGraw-HillGlencoe Algebra 1 is a key program in our vertically aligned high school mathematics series developed to help all students achieve a better understanding of mathematics and improve their mathematics...
-
A First Course in Abstract Algebra
By Joseph J. RotmanFor one-semester or two-semester undergraduate courses in Abstract Algebra. This new edition has been completely rewritten. The four chapters from the first edition are expanded, from 257 pages in first...
-
Algebra and Trigonometry with Analytic Geometry
By Earl Swokowski, Jeffery ColeClear explanations, an uncluttered and appealing layout, and examples and exercises featuring a variety of real-life applications have made this text popular among students year after year. This latest edition...
-
Study and Solutions Guide for College Algebra, Fourth Edition: Larson/Hostetler
By Ron Larson, Dianna L. ZookStudy and Solutions Guide for College Algebra, Fourth Edition: Larson/Hostetler