On Estimation Algorithms vs Approximation Algorithms

Abstract

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 some cases the design of approximation algorithms includes a
nonconstructive component. As a result, the algorithms become
estimation algorithms rather than approximation algorithms: they
allow one to estimate the value of the optimal solution, without
actually producing a solution whose value is close to optimal.

We shall present a few such examples, and discuss some open
questions.