The Design of Approximation Algorithms (David P. Williamson, et al)

 
0.0 (0)
The Design of Approximation Algorithms (David P. Williamson, et al)

Discrete optimization challenges can be found everywhere, including in traditional operations research planning issues like scheduling, facility location, and network design, as well as in database issues in computer science and viral marketing. But the majority of these issues are NP-hard.

Therefore, there are no effective algorithms to identify the best solutions to such problems unless P = NP. This book demonstrates how to create efficient algorithms that locate solutions that are demonstrably close to ideal.

The book is divided into sections based on key algorithmic methods for creating approximation algorithms, such as greedy and local search algorithms, dynamic programming, linear and semidefinite programming, randomization, and others.

The first section of the book devotes each chapter to a specific algorithmic technique, which is subsequently used to solve a number of diverse problems. The second section reviews the techniques but does it in a more in-depth manner.

The book also discusses techniques for demonstrating how difficult it is to tackle approximation optimization problems. The book will act as a reference for scholars interested in the heuristic solution of discrete optimization problems and is written as a textbook for graduate-level algorithms courses.

Ebook Details

About the Authors
  • David P. Williamson holds a combined post in the Department of Information Science and the School of Operations Research and Information Engineering at Cornell University.
  • At Cornell University, David Shmoys holds faculty positions in the Department of Computer Science and the School of Operations Research and Information Engineering.
Published
Published Date / Year
1 edition (2011); eBook (Manuscript)
Permission
Below you can download an electronic-only copy of the book. The electronic-only book is published on this website with the permission of Cambridge University Press
Hardcover
518 pages
eBook Format
PDF (500 pages)
ISBN-10
0521195276
ISBN-13
978-0521195270

Similar Programming & Computer Books

Éléments d'algorithmique - Algorithmic elements (D. Beauquier, et al)
This free programming book differs from other treatises on algorithms in two ways: first, we give special attention to the new tree structures that have emerged recently (bicolor trees,...
Complexité algorithmique - Algorithmic complexity (Sylvain Perifel)
The foundational ideas of algorithmic complexity theory are first covered in this free programming book before moving on to a number of more sophisticated subjects. ...
Algorithmique du texte - Text Algorithms (Maxime Crochemore, et al)
This free programming book offers a broad overview of text-processing algorithms. As such, it is an algorithmic book, but one whose goal is to utilize computers to manipulate language....
Strategic Foundations of General Equilibrium: Dynamic Matching and Bargaining Games (Douglas Gale)
Since Adam Smith's day, the theory of competition has played a significant role in economic study. This book, published by one of the most eminent modern economic theorists, details...
The Pure Logic Of Choice (Richard D. Fuerle)
A broad theory of economics based on free will is presented in this free programming book. The assumption that humans have free will and the ability to alter physical...
Price Theory: An Intermediate Text (David D. Friedman)
In order to help the reader grasp the economic way of thinking, the author first gives verbal, intuitive explanations of the topics before using graphs and/or calculus to illustrate...
Computer Arithmetic of Geometrical Figures: Algorithms and Hardware Design (S. I. Khmelnik)
This free programming book describes many iterations of processors made for affine transformations of planar and spatial many-dimensional figures. This processor is designed to perform affine transformations on geometrical...
Parallel Complexity Theory (Sanjeev Arora, et al.)
The focus of this free programming book is the research of Parallel Computing and Programming, which serves as an abstract indicator of the complexity of parallel computing problems. ...
Computational Complexity: A Conceptual Perspective (Oded Goldreich)
The study of the innate complexity of computer jobs is introduced conceptually in this free programming book. It is meant to be used as a textbook or for independent...
Computational Complexity (Wikibooks)
All computer science grads should read this free programming book since it offers information that is fundamental to their understanding of computation theory. ...

Others Programming Books by Cambridge University Press

Strategic Foundations of General Equilibrium: Dynamic Matching and Bargaining Games (Douglas Gale)
Since Adam Smith's day, the theory of competition has played a significant role in economic study. This book, published by one of the most eminent modern economic theorists, details...
Computational Complexity: A Conceptual Perspective (Oded Goldreich)
The study of the innate complexity of computer jobs is introduced conceptually in this free programming book. It is meant to be used as a textbook or for independent...
Algorithmic Number Theory: Lattices, Number Fields, Curves and Cryptography (Joe Buhler, et al)
One of the oldest and most fascinating branches of mathematics is number theory. Number theory has always involved computation, but this role has grown significantly over the past 20...
Combinatorial and Computational Geometry (Jacob E. Goodman, et al)
This volume, which consists of 32 papers on a variety of subjects of current research interest, is the result of the fusion of discrete and computational geometry. ...
Applied Combinatorics on Words (M. Lothaire)
This volume's goal is to provide a comprehensive analysis of some of the main areas in which combinatorics is applied. Core algorithms for text processing, natural language processing, audio...
Numerical Recipes in C: The Art of Scientific Computing, Second Edition (William H. Press, et al)
Numerical Recipes is a comprehensive handbook and reference on scientific computing and the result of a special partnership between four top researchers in academia and business. ...
Algebraic Combinatorics on Words (M. Lothaire)
Word-based combinatorics has independently developed within a variety of fields of mathematics, including number theory, group theory, and probability. It also commonly shows up in issues pertaining to theoretical...
Algebraic Topology (Allen Hatcher)
Algebraic topology is one of the three or four foundational first-year graduate mathematics courses at the majority of big universities.  
Model Theory, Algebra, and Geometry (Deirdre Haskell, et al)
Model theory is a subfield of mathematical logic that has found use in a variety of algebraic and geometric contexts.  
Classical Algebraic Geometry: A Modern View (Igor V. Dolgachev)
The robust general machinery created in the later half of the 20th century has been extremely helpful for algebraic geometry.  
Algorithms for Modular Elliptic Curves (J. E. Cremona)
Elliptic curves play a crucial and expanding role in computational number theory, where they are used extensively in processes like factorization, primality testing, and cryptography.
Random Graphs and Complex Networks (Remco van der Hofstad)
In this thorough introduction to network science, Random Graphs are used as representations of networks in the actual world. Such networks have unique empirical characteristics, and a plethora of...
Mathematical Illustrations: A Manual of Geometry and PostScript (Bill Casselman)
Anyone with a rudimentary understanding of coordinate geometry can benefit from this hands-on introduction to the methods required to create beautiful mathematical graphics.
Elementary Probability for Applications (Rick Durrett)
This engaging and accessible introduction to probability theory focuses on the findings that have the greatest practical value, such as Markov chains and combinatorial probability.
Advanced Data Analysis from an Elementary Point of View (Cosma Rohilla Shalizi)
For advanced undergraduate students who have already taken classes in probability, mathematical statistics, and linear regression, this textbook on data analysis methods is designed.
Categorical Homotopy Theory (Emily Riehl)
This book develops categorical abstract homotopy theory with a strong emphasis on instances.
Information Theory, Inference and Learning Algorithms (David J. C. MacKay)
Inference and information theory, which are frequently taught separately, are combined in this engaging textbook.
Probability on Trees and Networks (Russell Lyons, et al.)
This book focuses on a few discrete probability topics that are now under active development on infinite graphs. Naturally, analyses of finite graphs are also conducted, although typically with...
Engineering Design Optimization (Joaquim R. Martins, et al)
Humans have a knack for optimization. People are always looking for ways to make their lives and the systems around them better.
An Invitation to Applied Category Theory: Seven Sketches in Compositionality (Brendan Fong, et al)
Category Theory is unequaled in its capacity to arrange and layer abstractions and uncover commonalities across structures of all types. It is now proven to be a potent instrument...

User reviews

There are no user reviews for this listing.
Ratings
Rate this Book
Comments