Algorithms in a Nutshell

(^302) | Chapter 10: When All Else Fails
Approximation Algorithms
An approximation algorithm seeks answers that are close to, but not necessarily as
good as, the true answer. The general tradeoff is to decrease the time by which the
answer is returned at the expense of accuracy.
As an example of the speed improvement of solving problems when exact answers
aren’t necessary but good answers are acceptable, we consider the Traveling
Salesman Problem (TSP). In TSP, we are given a set of cities to visit and the set of
distances between each pair of cities. We must determine the least-costtourthat
starts at a city, visits each city exactly once, and returns to the originating city of
the tour. This problem is one of the most heavily researched of all problems in
computer science, and it is highly unlikely that there exists a polynomial time
algorithm that solves TSP; that is, no algorithm can solve TSP in O(nk) for fixed
integerk. It belongs to a large class of problems (theNP-hardproblems) for which
it is strongly believed that finding an exact answer is inherently very difficult.
But assuming it is known that the distances between locations satisfy the trian-
gular inequality (i.e., for all triples of locationsa,b,c, the distance fromatobis
never longer than the distance fromatocplus the distance fromctob), Christo-
fides (1976) designed an efficient algorithm to solve the problem that constructs a
tour that is never more than 50% longer than a shortest tour.
Offline Algorithms
We may batch instances of a problem to be solved all at once, as opposed to the
more usual assumption of online algorithms, in which each instance must be
solved as soon as it is presented.
As an example of the improvements in allowing offline algorithms, assume we
intend to implement a dictionary in which we insert a set ofnnumbersy 1 ...yn
into an initially empty dictionary and then performn/2 membership queries
contains(xi) for numbersx 1 ...xn/2. An optimal data structure to performninsert
operations followed by a singlecontains(xi) operation is to insert eachyjinto an
unordered arrayY, at a total cost O(n), and then implement thecontains(xi) query
with a SEQUENTIALSEARCHofxiin arrayYat a worst-case cost of O(n). The
total worst-case cost of then+1 operations is O(n).
Performing a sequence ofn/2 executions of SEQUENTIALSEARCHincurs a total
cost of O(n^2 ). Since there is no way to predict the queries that are to be
performed, an online algorithm cannot proactively take steps to minimize the
costs of a specific future query (note that an adversary can always thwart such
speedup attempts). However, if we batch the sequence ofn/2containsqueries for
offline processing, then we could sort the arrayYcontainingy 1 ...ynand sort an
arrayXcontainingx 1 ...xn/2, each at a worst-case cost of O(nlogn), and then
scan the two sorted arrays to seek duplicates, at a worst-case cost of O(n). By
permitting an offline algorithm to batch then/2 searches, we can solve the
sequence of problems in worst-case time O(nlogn); our costs are O(n^2 )ifwe
insist upon the online version in which each query must be processed before the
next query is read.
Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.
Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use