Increasing global competition, rapidly changing
markets, and greater consumer awareness have altered
the way in which corporations do business. To become
more efficient, many industries have sought to model
some operational aspects by gigantic optimization
problems. It is not atypical to encounter models
which capture 106 separate "yes" or "no"
decisions to be made. Although one could, in
principle, try all 210^6 possible solutions to
find the optimal one, such a method would be
impractically slow. Unfortunately, for most of these
models, no algorithms are known that find optimal
solutions with reasonable computation
times. Typically, industry must rely on solutions of
unguaranteed quality that are constructed in an ad
hoc manner. Fortunately, for some of these models
there are good approximation algorithms:
algorithms that produce solutions quickly that are
provably close to optimal. Over the past six years,
there have been a sequence of major breakthroughs in
our understanding of the design of approximation
algorithms and of limits to obtaining such
performance guarantees: this area has been one of
the most flourishing areas of discrete mathematics
and theoretical computer science.
