- [[Greedy Algorithms]] - [[TSP OPT Approximation Algorithm]] - [[Vertex Cover Approximation Algorithm]] - in optimization problems we are asked to find a solution with the maximum gain or the minimum cost - denote this optimum value (benefit or cost) by $OPT(I)$ - falls short of NP complete problem optimum, but never by too much - denote the approximation value on input $I$ as $A(I)$ - these algorithms are used to get near optimal solutions but in polynomial time - want to bound how far away from optimal it can get in worst case - the approximation ratio is then: - $\alpha = \frac{A{(I)}}{OPT{(I)}}$ - for the worst case scenario input $I$, the input that makes the approximate solution as far away from the actual optimum as possible - for a maximizing problem, ratio will be a fraction, goal is for $A(I)$ to reach the bigger bottom - for a minimizing problem, ratio will be a number gt;1$, goal is for $A(I)$ to reduce to the smaller bottom - in both cases the goal is to get a ratio of 1 for the value https://www.geeksforgeeks.org/approximation-algorithms/# https://people.eecs.berkeley.edu/~vazirani/algorithms/chap9.pdf https://www.youtube.com/watch?v=tutKR8AV23c&list=PLkFD6_40KJIyKLUW_4cm44mIdXSUpZry3&index=21