APPROXIMATION ALGORITHMS
INTRODUCTION An Approximate Algorithm is a way of approach NP-COMPLETENESS for the optimization problem. This technique does not guarantee the best solution. The goal of an approximation algorithm is to come as close as possible to the optimum value in a reasonable amount of time which is at the most polynomial time. Such algorithms are called approximation algorithm or heuristic algorithm. 1.For the travelling salesperson problem, the optimization problem is to find the shortest cycle , and the approximation problem is to find a short cycle . 2.For the vertex cover problem, the optimization problem is to find the vertex cover with fewest vertices , and the approximation problem is to find the vertex cover with few vertices. FEATURES OF APPROXIMATION ALGORITHM 1.An approximation algorithm guarantees to run in polynomial time though it does not guarantee the most effective solution. 2.An approximation algorithm guarantees to seek out high accuracy and top quality solutio...