This book shows how to design approximation algorithms: efficient algorithms that find provably near-optimal solutions. The book is organized around central algorithmic techniques for designing approximation algorithms, including greedy and local search algorithms, dynamic programming, linear and semidefinite programming, and randomization.
Integer Programming and Combinatorial OptimizationThe course is a comprehensive introduction to the theory, algorithms and applications of integer optimization and is organized in four parts: formulations and relaxations, algebra and geometry of integer optimization, algorithms for integer optimization, and extensions of integer optimization.
The Encyclopedia of Algorithms will provide a comprehensive set of solutions to important algorithmic problems for students and researchers interested in quickly locating useful information. The first edition of the reference will focus on high-impact solutions from the most recent decade; later editions will widen the scope of the work.
Triangulations: Structures for Algorithms and Applications
Triangulations appear everywhere, from volume computations and meshing to algebra and topology. This book studies the subdivisions and triangulations of polyhedral regions and point sets and presents the first comprehensive treatment of the theory of secondary polytopes and related topics. A central theme of the book is the use of the rich structure of the space of triangulations to solve computational problems
This text, extensively class-tested over a decade at UC Berkeley and UC San Diego, explains the fundamentals of algorithms in a story line that makes the material enjoyable and easy to digest. Emphasis is placed on understanding the crisp mathematical idea behind each algorithm, in a manner that is intuitive and rigorous without being unduly formal
