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 NP-complete
problems.2 Hence, there are no known polynomial-time algorithms for these
problems, and there are serious theoretical reasons to believe that such
algorithms do not exist. What then are our options for handling such problems,
many of which are of significant practical importance?
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 sa to a problem of minimizing some function f by the size of the relative error of this
approximation,
to make this ratio greater than or equal to 1,
as it is for minimization problems. Obviously, the closer r(sa) 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 r(sa). This leads to the following definitions.
DEFINITION
A
polynomial-time approximation algorithm is said to be a c-approximation algorithm, where c ≥ 1, if the accuracy ratio of the
approximation it produces does not exceed c for any instance of the problem in question:
The best (i.e., the smallest)
value of c for which inequality (12.3)
holds for all instances of the problem is called the performance ratio of the
algorithm and denoted RA.
The performance ratio serves
as the principal metric indicating the quality of the approximation algorithm.
We would like to have approximation algorithms with RA as close to 1 as possible. Unfortunately, as
we shall see, some approxima-tion algorithms have infinitely large performance
ratios (RA = ∞). This does not necessarily rule out using such
algorithms, but it does call for a cautious treatment of their outputs.
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.
Related Topics
Privacy Policy, Terms and Conditions, DMCA Policy and Compliant
Copyright © 2018-2023 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.