B. Apolloni, C. Ferretti, G. Mauri
Approximation of optimization problems and learnability.
Abstract
We study optimization problems in a context derived from the studies about
computational learnability. While an optimization problem can be hard
to solve, it could be easy to approximate. But when the degree of
approximation is checked by another approximating algorithm we can setup
an interaction protocol in which the task is to find the
power of the checker, a task similar to that of learning a secret concept.
The results are about relations between approximability and this new
kind of learnability.