Analysis of Algorithms : An Active Learning Approach

9.1 GREEDY APPROXIMATION ALGORITHMS 233

and Value(Soptimal)≥ Value(S) for all S∈ PSI if the problem is a maximization
problem.
Approximation algorithms for class NP problems will not necessarily find an
optimal solution because they will only look at a portion of the set PSI or will
construct potential solutions from just a small subset of PSI. We can determine
how good an approximation algorithm is by looking at the solution that the
algorithm produces relative to this optimal value. In some cases, we can deter-
mine the optimal value even if we cannot find a solution that will produce that
value. The quality of an approximation algorithm is then given by the equation

In some cases, it will matter whether we are considering cases that have a
fixed number of input values or cases that all have the same optimal solution.
In other words, do we look at how good an approximation algorithm is for
cases of 10 input values or different-sized input cases that all have an optimal
solution of 50? These two views can result in two different quality ratings.
The following subsections look at a few of the approximation algorithms for
the problems we have discussed. The algorithms given are not the only possi-
bilities but rather give you a feel for the range of techniques. All of these
approximations are polynomial time algorithms.

■ 9.1.1 Traveling Salesperson Approximations
There is a whole set of algorithms for various problems (including those in the
class P) that are classified as greedy algorithms. These algorithms always look at
the current situation and make the best choice based on the information avail-
able. Recall that the minimum spanning tree and shortest-path algorithms are
examples of greedy algorithms.
It would seem that we could just apply the shortest-path algorithm to solve
this problem, but it’s not quite as easy as that. Dijkstra’s algorithm is actually
interested in the shortest path between two nodes but does not necessarily go
through every node in the graph. We can, however, use this general greedy

QA()I

Value()AI()

Value---------------------------------()Soptimal for minimization problems

Value()Soptimal

Value()AI()

--------------------------------- for maximization problems















=