In this section, we discuss a different approach to handling difficult problems of combinatorial optimization, such as the traveling salesman problem and the knapsack problem.

**Approximation Algorithms for NP -Hard Problems**

In this section, we discuss a
different approach to handling difficult problems of combinatorial
optimization, such as the traveling salesman problem and the knapsack problem.
As we pointed out in Section 11.3, the decision versions of these problems are *NP-*complete. Their optimization versions
fall in the class of ** NP-hard problems**—problems that are
at least as hard as

If an instance of the problem
in question is very small, we might be able to solve it by an exhaustive-search
algorithm (Section 3.4). Some such problems can be solved by the dynamic
programming technique we demonstrated in Section 8.2. But even when this
approach works in principle, its practicality is limited by dependence on the
instance parameters being relatively small. The discovery of the
branch-and-bound technique has proved to be an important breakthrough, because
this technique makes it possible to solve many large instances of difficult
optimization problems in an acceptable amount of time. However, such good
performance cannot usually be guaranteed.

There is a radically
different way of dealing with difficult optimization prob-lems: solve them
approximately by a fast algorithm. This approach is particularly appealing for
applications where a good but not necessarily optimal solution will suffice.
Besides, in real-life applications, we often have to operate with inaccurate
data to begin with. Under such circumstances, going for an approximate solution
can be a particularly sensible choice.

Although approximation
algorithms run a gamut in level of sophistication, most of them are based on
some problem-specific heuristic. A ** heuristic** is a common-sense rule
drawn from experience rather than from a mathematically proved assertion. For
example, going to the nearest unvisited city in the traveling salesman problem
is a good illustration of this notion. We discuss an algorithm based on this
heuristic later in this section.

Of course, if we use an
algorithm whose output is just an approximation of the actual optimal solution,
we would like to know how accurate this approximation is. We can quantify the
accuracy of an approximate solution *s***_{a}** to a problem of minimizing some function

to make this ratio greater than or equal to 1,
as it is for minimization problems. Obviously, the closer *r(s*_{a}** )** is to 1, the better the approximate solution
is.

For most instances, however,
we cannot compute the accuracy ratio, because we typically do not know *f (s*^{∗}** )**, the true optimal value of the objective
function. Therefore, our hope should lie in obtaining a good upper bound on the
values of

**DEFINITION
**A
polynomial-time approximation algorithm is said to be a** **** c-approximation algorithm**, where

The best (i.e., the smallest)
value of ** c** for which inequality (12.3)
holds for all instances of the problem is called the

The performance ratio serves
as the principal metric indicating the quality of the approximation algorithm.
We would like to have approximation algorithms with *R***_{A}** as close to 1 as possible. Unfortunately, as
we shall see, some approxima-tion algorithms have infinitely large performance
ratios

There are two important facts
about difficult combinatorial optimization problems worth keeping in mind.
First, although the difficulty level of solving most such problems exactly is
the same to within a polynomial-time transforma-tion of one problem to another,
this equivalence does not translate into the realm of approximation algorithms.
Finding good approximate solutions is much easier for some of these problems
than for others. Second, some of the problems have special classes of instances
that are both particularly important for real-life appli-cations and easier to
solve than their general counterparts. The traveling salesman problem is a
prime example of this situation.

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Introduction to the Design and Analysis of Algorithms : Coping with the Limitations of Algorithm Power : Approximation Algorithms for NP -Hard Problems |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.