APPROXIMATION ALGORITHMS

Increasing global competition, rapidly changing markets, and greater c onsumer awareness have altered the way in which corporations do busine ss, To become more efficient, many industries have sought to model som e operational aspects by gigantic optimization problems, It is not aty pical to encounter models that capture 10(6) separate ''yes'' or ''no' ' decisions to be made, Although one could, in principle, try all 2(10 6) possible solutions to find the optimal one, such a method would be impractically slow. Unfortunately, for most of these models, no algori thms are known that find optimal solutions with reasonable computation times, Typically, industry must rely on solutions of unguaranteed qua lity that are constructed in an ad hoc manner, Fortunately, for some o f these models there are good approximation algorithms: algorithms tha t produce solutions quickly that are provably close to optimal, Over t he past 6 years, there has been a sequence of major breakthroughs in o ur understanding of the design of approximation algorithms and of limi ts to obtaining such performance guarantees; this area has been one of the most flourishing areas of discrete mathematics and theoretical co mputer science.