What can you do when a problem is NP-Complete?
Once a problem is known to be NP-Complete, it is
genreally a good idea to stop looking for a polynomial time algorithm to
solve the problem (the only way around this is to prove that P=NP, a result
which is widely believed among experts to be false). Thus what else
can you do with such a problem?
One answer is to try to approximate the solution.
That is, if it is known that finding an exact solution would be difficult,
we then loosen the objective of the problem somewhat. Instead of
looking for the best solution (which would probably take a long time to
find), we allow ourselves to find a solution which is not necessarily the
best, but is known to be within some ratio of the best solution.
This involves creating an algorithm which approximates the solution in
a polynomial amount of time, also known as an "approximation algorithm".
The following are some types of approximation algorithms
Polynomial Time Approximation Scheme
A polynomial time approximation scheme, or "PTAS",
is the next best thing to finding a polynomial time algorithm which solves
the problem. A PTAS is simply an algorithm which takes as an input,
the closeness of the approximation, and then can approximate the solution
to within that factor in a polynomial amount of time. That is, if
you tell me how closely to the best solution you want to answer the problem,
I can give you an algorithm which will achieve that approximation in a
polynomial amount of time. The actual polynomial may vary with the
closeness of the approximation. Generally, as the approximation ration
gets close to 1 (which would be an exact solution), the exponent in the
polynomial increases.
For example, the approximation ratio of a PTAS is
commonly described as (1 + e) where e
can be arbitrarily small. The running time of that PTAS might
then be O(n1/e). Notice that
as e gets smaller (an the approximation gets
better), the exponent of the running time increases, (and thus the overall
running time gets worse).
Constant Approximation
Often times when we are trying to solve the problem,
we are willing to settle for approximating the answer within some constant
ratio of the optimal answer. For example, consider that I cannot,
in a reasonable amount of time, find the best route for a salesman to visit
all the cities on my map. I may be willing to settle for a route
that is no more than twice as long as the best route, if that will allow
me to find the route in a polynomial amount of time. An algorithm
which is guaranteed to find such a route through any given list of cities
is called a 2-approximation.
Logarithmic Approximation
Sometimes a problem can be so difficult, that the
best known approximation algorithm cannot even guarantee to come withing
a constant ratio of the best answer. A logarithmic approximation
is just such an algorithm. The ratio of approximation of such an
algorithm will vary with the size of the problem. That is, as your
problem size increases, the ratio between your answer and the best answer
will also increase (as well as the amount of time it takes to find that
approximation). A logarithmic approximation will guarantee that the
approximation ratio is within O(lgn) of the best solution (where n is the
size of the input).