Understanding Approximation Algorithms: Types, Terminology, and Performance Ratios
Approximation algorithms aim to find near-optimal solutions for optimization problems, with the performance ratio indicating how close the algorithm's solution is to the optimal solution. The terminology used in approximation algorithms includes P (optimization problem), C (approximation algorithm), I (instance of P), C*(I) (optimal value for instance I), and C(I) (value of instance I generated by C). These algorithms are applicable to both minimization and maximization problems, with defined ratios for each case. The article explains key concepts and provides insights into different types and applications of approximation algorithms.
- Approximation algorithms
- Optimization problems
- Performance ratios
- Algorithm analysis
- Computer science
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Approximation Algorithms CS-209: Design and Analysis of Algorithm Instructor: Dr. Maria Anjum
Approximation Algorithms an algorithm that returns near-optimal solutions is called an approximation algorithm. an optimization problem in which each potential solution has a positive cost, and we wish to find a near-optimal solution. Depending on the problem, we may define an optimal solution as one with maximum possible cost or one with minimum possible cost; that is, the problem may be either a maximization or a minimization problem.
Approximation Algorithms Types and Applications Traveling sales person Knapsack Planar graph coloring Vertex cover problem
Approximation Algorithms Terminology: P: an optimization problem C: an approximation algorithm I: an instance of P C*(I): optimal value for instance I C(I): value of instance I generated by C
Approximation Algorithms Performance Ratio: a ratio between the result obtained by the algorithm and the optimal cost or profit. Typically this ratio is taken in whichever direction makes it bigger than one; for example, an algorithm that solves for a cost of $2 an instance of a problem that has an optimal cost of $1 has approximation ratio 2; but an algorithm that sells 10 airplane tickets (a profit of 10) when the optimum is 20 also has approximation ratio 2.
Approximation Algorithms a problem has an approximation ratio of p(n) if, for any input of size n, the cost C of the solution produced by the algorithm is within a factor of . p(n) of the cost C of an optimal solution: Terminology: P: an optimization problem C: an approximation algorithm I: an instance of P C*(I): optimal value for instance I The definitions of the approximation ratio and of a p(n) approximation algorithm apply to both minimization and maximization problems. C(I): value of instance I generated by C For a maximization problem, 0 < C C*, and the ratio C*/C gives the factor by which the cost of an optimal solution is larger than the cost of the approximate solution.
Approximation Algorithms Similarly, for a minimization problem, 0 < C* C, and the ratio C/C* gives the factor by which the cost of the approximate solution is larger than the cost of an optimal solution. Because we assume that all solutions have positive cost, these ratios are always well defined. The approximation ratio of an approximation algorithm is never less than 1, since C/C* 1 implies C*/C 1.
Approximation Algorithms Relative Error When the approximation ratio is close to 1, it is often more useful to look at the approximation error, which is defined as the approximation ratio minus 1.
Home Assignment Home Assignment Revisit 1/0 Knapsack problem.
References Book Introduction to algorithms, 3rd edition http://www.cs.yale.edu/homes/aspnes/pinewiki/ApproximationAlgorithms.html http://www.cs.umsl.edu/~sanjiv/classes/cs5130/lectures/approx.pdf http://www.iitg.ac.in/gkd/aie/slide/approximation-algorithms.pdf
