Approximation Algorithms

This book covers the dominant theoretical approaches to the approximate solution of hard combinatorial optimization and enumeration problems.

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

**Publication date**: 01 Jan 2003

**ISBN-10**:
n/a

**ISBN-13**:
9783540653677

**Paperback**:
396 pages

**Views**: 19,281

Approximation Algorithms

This book covers the dominant theoretical approaches to the approximate solution of hard combinatorial optimization and enumeration problems.

Excerpts from the Introduction:

This book deals with designing polynomial time approximation algorithms for NP-hard optimization problems. Typically, the decision versions of these problems are in NP, and are therefore NP-complete. From the viewpoint of exact solutions, all NP-complete problems are equally hard, since they are inter-reducible via polynomial time reductions. Typically, such a reduction maps optimal solutions of the given instance to optimal solutions of the transformed instance and preserves the number of solutions. Indeed, the counting versions of all known NP-complete problems are NP-complete, and typically the proof follows directly from the proof of NP-completeness.

The picture looks different when these problems are studied from the viewpoint of efficiently obtaining near-optimal solutions: polynomial time reductions do not preserve near-optimality of solutions, and NP-complete problems exhibit a rich set of possibilities, all the way from allowing approximability to any required degree, to essentially not allowing approximability at all.

A problem is polynomial time solvable only if it has the algorithmically relevant combinatorial structure that can be used as "footholds" to efficiently hone in on a solution. The process of designing a polynomial time algorithm is a two-pronged attack: unraveling this structure in the given problem, and finding algorithmic techniques that can exploit this structure.

Although NP-hard problems do not offer footholds to find optimal solutions efficiently, they may still offer footholds to find near-optimal solutions efficiently. So, at a high level, the process of designing approximation algorithms is not very different: it still involves unraveling relevant structure and finding algorithmic techniques to exploit it. Typically, the structure turns out to be more elaborate, and often, the algorithmic techniques result from generalizing and extending sonic of the powerful algorithmic tools developed in the study of exact algorithms. On the other hand, looking at this process a little more closely, one can see that it has its own general principles.

This book deals with designing polynomial time approximation algorithms for NP-hard optimization problems. Typically, the decision versions of these problems are in NP, and are therefore NP-complete. From the viewpoint of exact solutions, all NP-complete problems are equally hard, since they are inter-reducible via polynomial time reductions. Typically, such a reduction maps optimal solutions of the given instance to optimal solutions of the transformed instance and preserves the number of solutions. Indeed, the counting versions of all known NP-complete problems are NP-complete, and typically the proof follows directly from the proof of NP-completeness.

The picture looks different when these problems are studied from the viewpoint of efficiently obtaining near-optimal solutions: polynomial time reductions do not preserve near-optimality of solutions, and NP-complete problems exhibit a rich set of possibilities, all the way from allowing approximability to any required degree, to essentially not allowing approximability at all.

A problem is polynomial time solvable only if it has the algorithmically relevant combinatorial structure that can be used as "footholds" to efficiently hone in on a solution. The process of designing a polynomial time algorithm is a two-pronged attack: unraveling this structure in the given problem, and finding algorithmic techniques that can exploit this structure.

Although NP-hard problems do not offer footholds to find optimal solutions efficiently, they may still offer footholds to find near-optimal solutions efficiently. So, at a high level, the process of designing approximation algorithms is not very different: it still involves unraveling relevant structure and finding algorithmic techniques to exploit it. Typically, the structure turns out to be more elaborate, and often, the algorithmic techniques result from generalizing and extending sonic of the powerful algorithmic tools developed in the study of exact algorithms. On the other hand, looking at this process a little more closely, one can see that it has its own general principles.

Tweet

About The Author(s)

Vijay V. Vazirani is a Professor in the College of Computing at Georgia Institute of Technology. His research interests are algorithmic problems in mathematical economics and game theory, design of efficient exact and approximation algorithms, computational complexity theory.

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