Lecture Notes on Approximation Algorithms

Attempt to classify all hard optimization problems as one of the possibilities for relaxing the requirements, from the point of view of approximability: easy, intermediate and hard.

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

**Publication date**: 31 Dec 1992

**ISBN-10**:
n/a

**ISBN-13**:
n/a

**Paperback**:
136 pages

**Views**: 14,505

**Type**: N/A

**Publisher**:
n/a

**License**:
n/a

**Post time**: 25 Feb 2007 11:57:21

Lecture Notes on Approximation Algorithms

Attempt to classify all hard optimization problems as one of the possibilities for relaxing the requirements, from the point of view of approximability: easy, intermediate and hard.

Notes Excerpts:

A large number of (if not, most of) the optimization problems which are required to be solved in practice are NP-hard. Complexity theory tells us that it is impossible to find efficient algorithms for such problems unless P = NP, and this is very unlikely to be true. This does not obviate the need for solving these problems. Observe that NP-hardness only means that, if P <> NP, we cannot find algorithms which will find exactly the optimal solution to all instances of the problem in time which is polynomial in the size of the input. If we relax this rather stringent requirement, it may still be possible to solve the problem reasonably well.

There are three possibilities for relaxing the requirements outlined above to consider a problem well-solved in practice:

- Super-polynomial time heuristics. We may no longer require that the problem be solved in polynomial time. In some cases there are algorithms which are just barely super-polynomial and run reasonably fast in practice.

- Probabilistic analysis of heuristics. Another possibility is to drop the requirement that the solution to a problem cater equally to all input instances. In some applications, it is possible that the class of input instances is severely constrained and for these instances there is an efficient algorithm which will always do the trick.

- Approximation algorithms. Finally, we could relax the requirement that we always find the optimal solution. In practice, it is usually hard to tell the difference between an optimal solution and a near-optimal solution. It seems reasonable to devise algorithms which are really efficient in solving NP-hard problems, at the cost of providing solutions which in all cases is guaranteed to be only slightly sub-optimal

In some situations, the last relaxation of the requirements for solving a problem appears to be the most reasonable. This results in the notion of the "approximate" solution of an optimization problem.

In this book we will attempt to classify as one of three types all hard optimization problems, from the point of view of approximability. Some problems seem to be extremely easy to approximate, e.g. Knapsack, Scheduling and Bin Packing. Other problems are so hard that even finding very poor approximations can be shown to be NP-hard, e.g. Graph Coloring, TSP and Clique. Finally, there is a class of problems which seem to be of intermediate complexity, e.g. Vertex Cover, Euclidean TSP or Steiner Trees. In some cases we will be able to demonstrate that a problem is provably hard to approximate within some error.

A large number of (if not, most of) the optimization problems which are required to be solved in practice are NP-hard. Complexity theory tells us that it is impossible to find efficient algorithms for such problems unless P = NP, and this is very unlikely to be true. This does not obviate the need for solving these problems. Observe that NP-hardness only means that, if P <> NP, we cannot find algorithms which will find exactly the optimal solution to all instances of the problem in time which is polynomial in the size of the input. If we relax this rather stringent requirement, it may still be possible to solve the problem reasonably well.

There are three possibilities for relaxing the requirements outlined above to consider a problem well-solved in practice:

- Super-polynomial time heuristics. We may no longer require that the problem be solved in polynomial time. In some cases there are algorithms which are just barely super-polynomial and run reasonably fast in practice.

- Probabilistic analysis of heuristics. Another possibility is to drop the requirement that the solution to a problem cater equally to all input instances. In some applications, it is possible that the class of input instances is severely constrained and for these instances there is an efficient algorithm which will always do the trick.

- Approximation algorithms. Finally, we could relax the requirement that we always find the optimal solution. In practice, it is usually hard to tell the difference between an optimal solution and a near-optimal solution. It seems reasonable to devise algorithms which are really efficient in solving NP-hard problems, at the cost of providing solutions which in all cases is guaranteed to be only slightly sub-optimal

In some situations, the last relaxation of the requirements for solving a problem appears to be the most reasonable. This results in the notion of the "approximate" solution of an optimization problem.

In this book we will attempt to classify as one of three types all hard optimization problems, from the point of view of approximability. Some problems seem to be extremely easy to approximate, e.g. Knapsack, Scheduling and Bin Packing. Other problems are so hard that even finding very poor approximations can be shown to be NP-hard, e.g. Graph Coloring, TSP and Clique. Finally, there is a class of problems which seem to be of intermediate complexity, e.g. Vertex Cover, Euclidean TSP or Steiner Trees. In some cases we will be able to demonstrate that a problem is provably hard to approximate within some error.

Tweet

About The Author(s)

No information is available for this author.

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