What is an approximation oracle? 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.
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$.