On Estimation Algorithms vs Approximation Algorithms

Uriel Feige
In a combinatorial optimization problem, when given an input instance, one seeks a feasible solution that optimizes the value of the objective function. Many combinatorial optimization problems are NP-hard. A way of coping with NP-hardness is by considering approximation algorithms. These algorithms run in polynomial time, and their performance is measured by their approximation ratio: the worst case ratio between the value of the solution produced and the value of the (unknown) optimal solution. In...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.