ABSTRACT
This chapter discusses the basic methodologies and apply them to classic problems. These methodologies include the four major ones: restriction, relaxation, rounding, and transformation. The chapter examines inapproximability and shows that the “original” version of the traveling salesperson problem is constant ratio inapproximable. Another traditional method to generate suboptimal solutions is to apply greedy algorithms. The idea is to generate a solution by making a sequence of irrevocable decisions. Another traditional method to generate suboptimal solutions is to apply greedy algorithms. The idea is to generate a solution by making a sequence of irrevocable decisions. Linear program has also been used as a tool to compute the approximation ratio of some algorithms. This type of research may eventually be called the automatic analysis of approximation algorithms. Since the algorithm takes polynomial time with respect to the number of vertices and edges in the graph, it then follows that the algorithm solves in polynomial time the Hamiltonian cycle problem.
