Latest Movie :

The Design of Approximation Algorithms - David P. Williamson & David B. Shmoys

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-1990s, we sat down and wrote out an outline of the book. Then one of us (DPW), who was at the time an IBM Research Staff Member, taught several iterations of the course following the outline we had devised, in Columbia University’s Department of Industrial Engineering and Operations Research 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 to the book; we taught additional iterations of the course at Cornell in Fall 2006 and Fall 2009 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, this book is a way for 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.”

Contenido: [500 Pag.]

I. An Introduction to the techniques
1. An introduction to approximation algorithms
2. Greedy algorithms and local search
3. Rounding data and dynamic programming
4. Deterministic runding of linear programs
5. Random sampling  and randomized rounding of linear programs
6. Randomized  rpunding of semidefinite programs
7. The primal-dual method
8. Cuts and metrics 
II. Further uses of the techniques
9. Further uses of greedy and local search algorithms
10. Further uses of rounding data and dynamic programming
11. Further uses of deterministic rounding of linear programs
12. Further uses of random sampling and randomized rounding of linear programs
13. Further uses of randomized rounding of semidefinite programs
14. Further uses of the primal-dual method
15. Further uses of cuts and metrics
16. Techniques in proving the hardness of approximation
17. Open Problems
A. Linear programming
B. NP- completeness
Author index

Enlace de Descarga: [2.3 MB]

Share this article :

Publicar un comentario

Support : Creating Website | Adictec Perú | Ing. Alexis Llontop
Copyright © 2015. Download Xynior - All Rights Reserved
Template Created by Creating Website Published by Mas Template
Proudly powered by Blogger