ABSTRACT

Approximation algorithms were formally introduced in the 1960s to generate near-optimal solutions to optimization problems that could not be solved efficiently by the computational techniques available at that time. With the advent of the theory of NP-completeness in the early 1970s, the area became more prominent as the need to generate near-optimal solutions for NP-hard optimization problems became the most important avenue for dealing with computational intractability. As it was established in the 1970s, for some problems it is possible to generate near-optimal solutions quickly, whereas for other problems generating provably good suboptimal solutions is as difficult as generating optimal ones. Computational approaches based on probabilistic analysis and randomized algorithms became popular in the 1980s. The introduction of new techniques to solve linear programming problems started a new wave of approximation algorithms that matured and saw tremendous growth in the 1990s. There were a few techniques introduced in the 1980s and 1990s to deal, in the practical sense, with inapproximable problems. These methodologies have been referred to as metaheuristics and include Simulated Annealing (SA), Ant Colony Optimization (ACO), Evolutionary Computation (EC), Tabu Search (TS), Memetic Algorithms (MAs), and so on. Other previously established methodologies such as local search, backtracking, and branch-and-bound were also explored at that time. There has been a tremendous amount of research in metaheuristics during the past three decades. These techniques have been evaluated experimentally and have demonstrated their usefulness for solving problems that are arising in practice. During the last 25 years or so, approximation algorithms have attracted considerably more attention. This was a result of a stronger inapproximability methodology that could be applied to a wider range of problems and the development of new approximation algorithms for problems arising in established and emerging application areas. Polynomial Time Approximation 2Schemes (PTASs) were introduced in the 1960s and the more powerful Fully Polynomial Approximation Schemes (FPTASs) were introduced in the 1970s. Asymptotic PTAS (APTAS) and Asymptotic FPTAS (AFPTAS), and Fully Polynomial Randomized Approximation Schemes (FPRASs) were introduced later on.