Design and Analysis of Algorithms
Selected Reading
- DAA - Discussion
- DAA - Useful Resources
- DAA - Quick Guide
- DAA - Hill Climbing Algorithm
- NP Hard & NP-Complete Classes
- DAA - Cook’s Theorem
- DAA - P and NP Class
- DAA - Vertex Cover
- DAA - Max Cliques
- Deterministic vs. Nondeterministic Computations
- DAA - Sublist Search
- DAA - Fibonacci Search
- DAA - Exponential Search
- DAA - Jump Search
- DAA - Interpolation Search
- DAA - Binary Search
- DAA - Linear Search
- Searching Techniques Introduction
- DAA - Radix Sort
- DAA - Counting Sort
- DAA - Bucket Sort
- DAA - Heap Sort
- DAA - Shell Sort
- DAA - Selection Sort
- DAA - Insertion Sort
- DAA - Bubble Sort
- DAA - Extract Method
- DAA - Heapify Method
- DAA - Insert Method
- DAA - Binary Heap
- Optimal Cost Binary Search Trees
- DAA - Multistage Graph
- DAA - Shortest Paths
- DAA - Spanning Tree
- Travelling Salesperson Approximation Algorithm
- Set Cover Problem
- Vertex Cover Problem
- Approximation Algorithms
- Fisher-Yates Shuffle
- Karger’s Minimum Cut
- Randomized Quick Sort
- Randomized Algorithms
- Travelling Salesman Problem | Dynamic Programming
- Longest Common Subsequence
- DAA - 0-1 Knapsack
- Floyd Warshall Algorithm
- Matrix Chain Multiplication
- DAA - Dynamic Programming
- DAA - Optimal Merge Pattern
- DAA - Job Sequencing with Deadline
- DAA - Fractional Knapsack
- Map Colouring Algorithm
- Dijkstra’s Shortest Path Algorithm
- Kruskal’s Minimal Spanning Tree
- Travelling Salesman Problem
- DAA - Greedy Method
- Towers of Hanoi
- Karatsuba Algorithm
- Strassen’s Matrix Multiplication
- DAA - Binary Search
- DAA - Merge Sort
- DAA - Max-Min Problem
- DAA - Divide & Conquer
- DAA - Space Complexities
- Master’s Theorem
- Time Complexity
- Asymptotic Notations & Apriori Analysis
- DAA - Methodology of Analysis
- DAA - Analysis of Algorithms
- DAA - Introduction
- Home
Selected Reading
- Who is Who
- Computer Glossary
- HR Interview Questions
- Effective Resume Writing
- Questions and Answers
- UPSC IAS Exams Notes
Approximation Algorithms
Design and Analysis - Approximation Algorithms
Approximation algorithms are algorithms designed to solve problems that are not solvable in polynomial time for approximate solutions. These problems are known as NP complete problems. These problems are significantly effective to solve real world problems, therefore, it becomes important to solve them using a different approach.
NP complete problems can still be solved in three cases: the input could be so small that the execution time is reduced, some problems can still be classified into problems that can be solved in polynomial time, or use approximation algorithms to find near-optima solutions for the problems.
This leads to the concept of performance ratios of an approximation problem.
Performance Ratios
The main idea behind calculating the performance ratio of an approximation algorithm, which is also called as an approximation ratio, is to find how close the approximate solution is to the optimal solution.
The approximate ratio is represented using ρ(n) where n is the input size of the algorithm, C is the near-optimal solution obtained by the algorithm, C* is the optimal solution for the problem. The algorithm has an approximate ratio of ρ(n) if and only if −
$$maxleft{frac{C}{C^{ast} },frac{C^{ast }}{C} ight}leq ho left ( n ight )$$
The algorithm is then called a ρ(n)-approximation algorithm. Approximation Algorithms can be appped on two types of optimization problems: minimization problems and maximization problems. If the optimal solution of the problem is to find the maximum cost, the problem is known as the maximization problem; and if the optimal solution of the problem is to find the minimum cost, then the problem is known as a minimization problem.
For maximization problems, the approximation ratio is calculated by C*/C since 0 ≤ C ≤ C*. For minimization problems, the approximation ratio is calculated by C/C* since 0 ≤ C* ≤ C.
Assuming that the costs of approximation algorithms are all positive, the performance ratio is well defined and will not be less than 1. If the value is 1, that means the approximate algorithm generates the exact optimal solution.
Examples
Few popular examples of the approximation algorithms are −
Vertex Cover Problem
Set Cover Problem
Travelpng Salesperson Problem
The Subset Sum Problem