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. Local search techniques have a long history; they range from simple constructive and iterative improvement algorithms to rather complex methodologies that require significant fine-tuning, such as evolutionary algorithms (EAs) or SA. Local search is perhaps one of the most natural ways to attempt to find an optimal or suboptimal solution to an optimization problem. There are many different ways one can use to judge algorithms. The main ones use are the time and space required to solve the problem. This is normally expressed in terms of n, the input size.
