The Design of Approximation Algorithms

This book is designed to be a textbook for graduate-level courses in approximation algorithms. It assumes familiarity with algorithms, mathematical proofs about the correctness of algorithms, probability theory and NP-completeness.

**Tag(s):**
Theory of Computation

**Publication date**: 26 Apr 2011

**ISBN-10**:
0521195276

**ISBN-13**:
9780521195270

**Paperback**:
518 pages

**Views**: 11,875

The Design of Approximation Algorithms

This book is designed to be a textbook for graduate-level courses in approximation algorithms. It assumes familiarity with algorithms, mathematical proofs about the correctness of algorithms, probability theory and NP-completeness.

License:

Excerpts from the Preface:

David P. Williamson wrote:This electronic-only manuscript is published on www.designofapproxalgs.com with the permission of Cambridge University Press. One copy per user may be taken for personal use only and any other use you wish to make of the work is subject to the permission of Cambridge University Press (rights@cambridge.org). You may not post this file on any other website.

Excerpts from the Preface:

David P. Williamson wrote:This book is designed to be a textbook for graduate-level courses in approximation algorithms. After some experience teaching minicourses in the area in the mid-90s, we sat down and wrote out an outline of the book. Then I (DPW), at the time an IBM Research Staff Member, taught several iterations of the course following the outline we had devised, in Columbia University's Industrial Engineering and Operations Research department in Spring 1998, in Cornell University's School of Operations Research and Industrial Engineering in Fall 1998 and at the Massachusetts Institute of Technology's Laboratory for Computer Science in Spring 2000. The lecture notes from these courses were made available, and we got enough positive feedback on them from students and from professors teaching such courses elsewhere that we felt we were on the right track. Since then, there have been many exciting developments in the area, and we have added many of them into our book; I taught additional iterations of the course at Cornell in Fall 2006 and Fall 2009 (this time as a Cornell faculty member) in order to field test some of the writing of the newer results.

The courses were developed for students who have already had a class, undergraduate or graduate, in algorithms, and who were comfortable with the idea of mathematical proofs about the correctness of algorithms. The book assumes this level of preparation. The book also assumes some basic knowledge of probability theory (for instance, how to compute the expected value of a discrete random variable). Finally, we assume that the reader knows something about NP-completeness, at least enough to know that there might be good reason for wanting fast, approximate solutions to NP-hard discrete optimization problems. At one or two points in the book, we do an NP-completeness reduction to show that it can be hard to find approximate solutions to such problems; we include a short appendix on the problem class NP and the notion of NP-completeness for those unfamiliar with the concepts. However, the reader unfamiliar with such reductions can also safely skip over such proofs.

In addition to serving as a graduate textbook, we have also envisioned the book as a way tor students to get the background to read current research in the area of approximation algorithms. In particular, we wanted a book that we could hand our own Ph.D. students just starting in the field, and say "Here, read this."

We further hope that the book will serve as a reference to the area of approximation algorithms for researchers who are generally interested in the heuristic solution of discrete optimization problems; such problems appear in areas as diverse as traditional operations research planning problems (such as facility location and network design) to computer science problems in database and programming language design to advertising issues in viral marketing. We hope that the book helps researchers understand the techniques available in the area of approximation algorithms for approaching such problems.

Tweet

About The Author(s)

David B. Shmoys is Laibe/Acheson Professor of Business Management & Leadership Studies in the School of Operations Research and Information Engineering at Cornell University. The primary focus of his research is on the design and analysis of efficient algorithms for discrete optimization problems, and in particular, on approximation algorithms for NP-hard and other computationally intractable problems.

David P. Williamson is a Professor at Cornell University in the School of Operations Research and Information Engineering. He received his Ph.D. in Computer Science from MIT under Professor Michel X. Goemans in 1993. His research focuses on finding efficient algorithms for hard discrete optimization problems, with a focus on approximation algorithms for problems in network design, facility location, and scheduling. Other interests include algorithms for information networks.

Book Categories

Computer Science
Introduction to Computer Science
Introduction to Computer Programming
Algorithms and Data Structures
Artificial Intelligence
Computer Vision
Machine Learning
Neural Networks
Game Development and Multimedia
Data Communication and Networks
Coding Theory
Computer Security
Information Security
Cryptography
Information Theory
Computer Organization and Architecture
Operating Systems
Image Processing
Parallel Computing
Concurrent Programming
Relational Database
Document-oriented Database
Data Mining
Big Data
Data Science
Digital Libraries
Compiler Design and Construction
Functional Programming
Logic Programming
Object Oriented Programming
Formal Methods
Software Engineering
Agile Software Development
Information Systems
Geographic Information System (GIS)

Mathematics
Mathematics
Algebra
Abstract Algebra
Linear Algebra
Number Theory
Numerical Methods
Precalculus
Calculus
Differential Equations
Category Theory
Proofs
Discrete Mathematics
Theory of Computation
Graph Theory
Real Analysis
Complex Analysis
Probability
Statistics
Game Theory
Queueing Theory
Operations Research
Computer Aided Mathematics

Supporting Fields
Web Design and Development
Mobile App Design and Development
System Administration
Cloud Computing
Electric Circuits
Embedded System
Signal Processing
Integration and Automation
Network Science
Project Management

Operating System
Programming/Scripting
Ada
Assembly
C / C++
Common Lisp
Forth
Java
JavaScript
Lua
Microsoft .NET
Rexx
Perl
PHP
Python
R
Rebol
Ruby
Scheme
Tcl/Tk

Miscellaneous
Sponsors