# Approximation Algorithms
Gets a solution that is not necessarily optimal but hopefully close to it
## Accuracy Ratio of Approximate Solutions
$r(s_a)=f(s_a)/f(s^{*})$ for minimization problems
$r(s_a)=f(s^{*})/f(s_a)$ for maximization problems
$f(s_a)$ and $f(s^{*})$ are values of the objective function f for the approximate solution $s_a$ and actual optimal solution $s^{*}$

## Performance ratio of the algorithm
- The lowest upper bound of r($s_a$) on all instances

Provides a polynomial time solution for a problem that can't normally be solved in polynomial time