Approximation-preserving reduction

In computability theory and computational complexity theory, especially the study of approximation algorithms, an approximation-preserving reduction is an algorithm for transforming one optimization problem into another problem, such that the distance of solutions from optimal is preserved to some degree. Approximation-preserving reductions are a subset of more general reductions in complexity theory; the difference is that approximation-preserving reductions usually make statements on approximation problems or optimization problems, as opposed to decision problems. Intuitively, problem A is reducible to problem B via an approximation-preserving reduction if, given an instance of problem A and a (possibly approximate) solver for problem B, one can convert the instance of problem A into an instance of problem B, apply the solver for problem B, and recover a solution for problem A that also has some guarantee of approximation. Unlike reductions on decision problems, an approximation-preserving reduction must preserve more than the truth of the problem instances when reducing from one problem to another. It must also maintain some guarantee on the relationship between the cost of the solution to the cost of the optimum in both problems. To formalize: Let A and B be optimization problems. Let x be an instance of problem A, with optimal solution . Let denote the cost of a solution y to an instance x of problem A. This is also the metric used to determine which solution is considered optimal. An approximation-preserving reduction is a pair of functions (which often must be computable in polynomial time), such that: f maps an instance x of A to an instance of B. g maps a solution of B to a solution y of A. g preserves some guarantee of the solution's performance, or approximation ratio, defined as . There are many different types of approximation-preserving reductions, all of which have a different guarantee (the third point in the definition above).