I have seen the term "approximation oracle" in computer science papers, sometimes parameterized with the letters $\alpha$ and $\beta$. What is an approximation oracle? How are such oracles used? I am somewhat familiar with the idea of an "oracle machine" in complexity theory.
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
An approximation oracle for an optimization problem $X$ is an oracle which accepts an instance of $X$ and returns an approximate optimum. The parameters $\alpha,\beta$ quantify the quality of the approximation.
Approximation oracles are a formal way of stating results of the following form:
Given a polynomial time $C$-approximation algorithm for $X$, there is a polynomial time $f(C)$-approximation algorithm for $Y$.
Formally, we give a polynomial time $f(C)$-approximation algorithm for $Y$ which uses a $C$-approximation oracle for $X$.
answered Jun 9, 2017 at 21:54