Ebook: Approximation Algorithms

This book covers the dominant theoretical approaches to the approximate solution of hard combinatorial optimization and enumeration problems. It contains elegant combinatorial theory, useful and interesting algorithms, and deep results about the intrinsic complexity of combinatorial problems. Its clarity of exposition and excellent selection of exercises will make it accessible and appealing to all those with a taste for mathematics and algorithms.

Richard Karp,University Professor, University of California at Berkeley

Following the development of basic combinatorial optimization techniques in the 1960s and 1970s, a main open question was to develop a theory of approximation algorithms. In the 1990s, parallel developments in techniques for designing approximation algorithms as well as methods for proving hardness of approximation results have led to a beautiful theory. The need to solve truly large instances of computationally hard problems, such as those arising from the Internet or the human genome project, has also increased interest in this theory. The field is currently very active, with the toolbox of approximation algorithm design techniques getting always richer.

It is a pleasure to recommend Vijay Vazirani's well-written and comprehensive book on this important and timely topic. I am sure the reader will find it most useful both as an introduction to approximability as well as a reference to the many aspects of approximation algorithms.

László Lovász, Senior Researcher, Microsoft Research

---

 This book covers the dominant theoretical approaches to the approximate solution of hard combinatorial optimization and enumeration problems. It contains elegant combinatorial theory, useful and interesting algorithms, and deep results about the intrinsic complexity of combinatorial problems. Its clarity of exposition and excellent selection of exercises will make it accessible and appealing to all those with a taste for mathematics and algorithms.

Richard Karp,University Professor, University of California at Berkeley

Following the development of basic combinatorial optimization techniques in the 1960s and 1970s, a main open question was to develop a theory of approximation algorithms. In the 1990s, parallel developments in techniques for designing approximation algorithms as well as methods for proving hardness of approximation results have led to a beautiful theory. The need to solve truly large instances of computationally hard problems, such as those arising from the Internet or the human genome project, has also increased interest in this theory. The field is currently very active, with the toolbox of approximation algorithm design techniques getting always richer.

It is a pleasure to recommend Vijay Vazirani's well-written and comprehensive book on this important and timely topic. I am sure the reader will find it most useful both as an introduction to approximability as well as a reference to the many aspects of approximation algorithms.

L?szl? Lov?sz, Senior Researcher, Microsoft Research

---

 This book covers the dominant theoretical approaches to the approximate solution of hard combinatorial optimization and enumeration problems. It contains elegant combinatorial theory, useful and interesting algorithms, and deep results about the intrinsic complexity of combinatorial problems. Its clarity of exposition and excellent selection of exercises will make it accessible and appealing to all those with a taste for mathematics and algorithms.

Richard Karp,University Professor, University of California at Berkeley

Following the development of basic combinatorial optimization techniques in the 1960s and 1970s, a main open question was to develop a theory of approximation algorithms. In the 1990s, parallel developments in techniques for designing approximation algorithms as well as methods for proving hardness of approximation results have led to a beautiful theory. The need to solve truly large instances of computationally hard problems, such as those arising from the Internet or the human genome project, has also increased interest in this theory. The field is currently very active, with the toolbox of approximation algorithm design techniques getting always richer.

It is a pleasure to recommend Vijay Vazirani's well-written and comprehensive book on this important and timely topic. I am sure the reader will find it most useful both as an introduction to approximability as well as a reference to the many aspects of approximation algorithms.

L?szl? Lov?sz, Senior Researcher, Microsoft Research

Content:
Front Matter....Pages I-XIX
Introduction....Pages 1-11
Front Matter....Pages 13-13
Set Cover....Pages 15-26
Steiner Tree and TSP....Pages 27-37
Multiway Cut and k-Cut....Pages 38-46
Feedback Vertex Set....Pages 47-53
Shortest Superstring....Pages 54-60
Knapsack....Pages 61-67
Bin Packing....Pages 68-73
Minimum Makespan Scheduling....Pages 74-78
Euclidean TSP....Pages 79-83
Front Matter....Pages 84-89
Introduction to LP-Duality....Pages 91-91
Set Cover via Dual Fitting....Pages 93-107
Rounding Applied to Set Cover....Pages 108-117
Set Cover via the Primal-Dual Schema....Pages 118-123
Maximum Satisfiability....Pages 124-129
Scheduling on Unrelated Parallel Machines....Pages 130-138
Multicut and Integer Multicommodity Flow in Trees....Pages 139-144
Multiway Cut....Pages 145-153
Multicut in General Graphs....Pages 154-166
Front Matter....Pages 167-178
Sparsest Cut....Pages 91-91
Steiner Forest....Pages 179-196
Steiner Network....Pages 197-211
Facility Location....Pages 212-230
Semidefinite Programming....Pages 231-241
Front Matter....Pages 242-254
Shortest Vector....Pages 255-269
Counting Problems....Pages 271-271
Hardness of Approximation....Pages 273-293
Open Problems....Pages 294-305
Back Matter....Pages 306-333
....Pages 334-343