6
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.