Approximation-preserving reduction

An approximation-preserving reduction is a transformation between optimization problems that controls how the approximation error of a solution changes under the transformation. It extends the role of a polynomial-time reduction from exact computational complexity to the classification of problems according to the quality of solutions obtainable in polynomial time.

The central requirement is quantitative rather than solely decision-theoretic. An instance of one optimization problem is mapped to an instance of another, and an approximate solution to the transformed instance is mapped back to a feasible solution of the original instance. The reduction specifies a bound relating the two approximation ratios. Consequently, an approximation algorithm for the target problem induces an approximation algorithm for the source problem with a controlled loss of accuracy.

Mathematical setting

Let (A) and (B) be optimization problems in NPO, the class of optimization problems whose feasible solutions have polynomially bounded representations, whose feasibility can be checked in polynomial time, and whose objective values can be computed in polynomial time. For an instance (x) of (A), write

[ \operatorname{OPT}_A(x) ]

for its optimal objective value. If (s) is a feasible solution, its objective value is denoted by (m_A(x,s)).

When objective values are positive, the approximation ratio can be represented symmetrically as

[ R_A(x,s)= \max\left{ \frac{m_A(x,s)}{\operatorname{OPT}_A(x)}, \frac{\operatorname{OPT}_A(x)}{m_A(x,s)} \right}. ]

This definition applies uniformly to maximization and minimization problems and satisfies (R_A(x,s)\geq 1). A solution is an (r)-approximation when its ratio is at most (r). Problems admitting polynomial-time algorithms with a constant approximation ratio form the class APX, while problems admitting arbitrarily accurate polynomial-time approximation algorithms form PTAS.

Ratio-based definitions require separate conventions when zero or negative objective values are permitted. In those settings, approximation-preserving reductions are formulated using normalized errors, additive guarantees, or problem-specific performance measures rather than an undefined quotient.

Formal definition

A standard approximation-preserving reduction, abbreviated AP-reduction, from (A) to (B) consists of two algorithms (f) and (g), together with a positive constant (\alpha). For every instance (x) of (A) and every rational number (r>1), the first algorithm constructs an instance

[ f(x,r) ]

of (B). Given a feasible solution (y) of that instance, the second algorithm constructs a feasible solution

[ g(x,y,r) ]

of (A). For each fixed value of (r), both transformations run in time polynomial in the size of (x) and the representation of (y).

The approximation condition is

[ R_B(f(x,r),y)\leq r \quad\Longrightarrow\quad R_A(x,g(x,y,r))\leq 1+\alpha(r-1). ]

Thus, an error of (r-1) in the target problem becomes an error of at most (\alpha(r-1)) in the source problem. The constant (\alpha) does not depend on the instance or on the requested approximation ratio.

The notation

[ A\leq_{\mathrm{AP}} B ]

indicates the existence of such a reduction. This relation is reflexive and transitive. Under composition, the instance transformations and solution transformations are combined, while the corresponding error-transfer constants multiply. AP-reducibility therefore induces equivalence classes and hardness notions within approximation complexity.

An alternative tolerance formulation uses a function (\delta(\varepsilon)). In that presentation, a ((1+\delta(\varepsilon)))-approximate solution for the target instance must yield a ((1+\varepsilon))-approximate solution for the source instance. The constant-factor definition obtains this form by taking (\delta(\varepsilon)=\varepsilon/\alpha).

Preservation of approximability

The principal consequence of an AP-reduction is the transfer of approximation schemes. Suppose that (A\leq_{\mathrm{AP}}B) with constant (\alpha), and that (B) has a polynomial-time approximation scheme. For a requested source accuracy (1+\varepsilon), the scheme for (B) is applied with target ratio

[ r=1+\frac{\varepsilon}{\alpha}. ]

The reconstructed solution then has approximation ratio at most (1+\varepsilon) for (A). It follows that membership of (B) in PTAS implies membership of (A) in PTAS.

A similar argument transfers constant-factor approximability. If (B) has a polynomial-time (c)-approximation for a fixed (c), then the induced algorithm for (A) has ratio at most

[ 1+\alpha(c-1). ]

Accordingly, AP-reductions support completeness results for APX. A problem (B) is APX-hard under AP-reductions when every problem in APX reduces to (B), and it is APX-complete when it is also a member of APX.

The basic definition does not necessarily preserve membership in FPTAS. Its running-time condition is polynomial for every fixed ratio (r), but it need not be polynomial in (1/(r-1)). Reductions intended to preserve fully polynomial approximation schemes impose an explicit polynomial bound on the dependence upon the accuracy parameter.

AP-reducibility also does not by itself transfer exact solvability. The definition concerns every fixed (r>1) and does not require meaningful behavior at (r=1). Reductions preserving exact optimality use additional constraints on objective values and reconstruction.

Historical development

Approximation-preserving reducibility developed alongside the systematic classification of hard optimization problems during the late twentieth century. Early reductions between optimization problems often established only that exact polynomial-time solvability would transfer. Their constructions could distort objective values sufficiently that an approximate target solution provided no bounded approximation for the source problem.

During 1994, You Watanabe formulated the tolerance-parameter version of AP-reducibility for NPO problems, separating the transformation of instances from the reconstruction of approximate solutions. The formulation expressed approximation loss as a function of the requested accuracy and supplied a direct composition rule for chains of reductions. Its ratio-linear specialization corresponds to the constant-(\alpha) definition used in later APX classifications.

The development of these reductions accompanied work on structurally restricted optimization classes. In particular, MAX SNP provided an early framework in which complete problems could be identified by reductions preserving constant-factor approximability. Subsequent classifications used AP-reductions and related transformations to distinguish problems admitting approximation schemes from problems whose approximation behavior remained APX-hard.

Relation to L-reductions

An L-reduction, introduced by Christos Papadimitriou and Mihalis Yannakakis in their analysis of MAX SNP, imposes direct linear bounds on optimal values and on absolute solution error. An L-reduction from (A) to (B) consists of polynomial-time mappings (f) and (g), together with positive constants (a) and (b), such that

[ \operatorname{OPT}_B(f(x)) \leq a,\operatorname{OPT}_A(x) ]

and

[ \left| \operatorname{OPT}_A(x)-m_A(x,g(y)) \right| \leq b\left| \operatorname{OPT}_B(f(x))-m_B(f(x),y) \right|. ]

The first inequality prevents the transformed optimum from becoming disproportionately large relative to the original optimum. The second inequality bounds the reconstructed solution error by the error present in the target solution.

For positive-valued problems, these conditions yield a multiplicative approximation bound and therefore imply an AP-style reduction. L-reductions are more restrictive because they control objective values through fixed linear inequalities rather than through a parameterized approximation guarantee. This additional structure makes them suitable for transferring explicit inapproximability constants.

The distinction matters when transformations introduce offsets or nonlinear rescaling. Such transformations can preserve the existence of a PTAS even when they fail the first inequality required by an L-reduction. AP-reductions accommodate these cases as long as the final approximation ratio remains controlled.

Relation to other reduction types

A PTAS-reduction retains the central implication that a PTAS for the target problem produces a PTAS for the source problem, but it permits a more general relationship between the two accuracy parameters. The function (\delta(\varepsilon)) need not be linear, provided that it is effectively computable and that the reduction has the required polynomial running time for each fixed accuracy.

An error-preserving reduction places stronger restrictions on the relationship between normalized objective errors. Such reductions support classifications in which the precise asymptotic degradation of the approximation ratio is significant. Their additional conditions can also preserve approximation schemes whose running times depend polynomially on the inverse error.

A gap-preserving reduction transforms a promise that the source optimum lies on one side of a threshold into a corresponding promise for the target problem. Gap reductions are commonly used in conjunction with the PCP theorem to prove that approximating a problem within a specified factor is NP-hard. Unlike an AP-reduction, a gap reduction need not reconstruct a feasible source solution from an arbitrary approximate target solution.

Approximation-preserving reductions also differ from Turing reductions that make repeated adaptive calls to an approximation procedure. The standard AP definition uses a many-one instance transformation followed by a solution reconstruction. Oracle-based approximation reductions form a broader family and require separate closure and composition conditions.

Role in completeness theory

Completeness under AP-reductions organizes optimization problems by the approximation guarantees that polynomial-time algorithms can achieve. If an APX-complete problem has a PTAS, every problem in APX has a PTAS through the corresponding reductions. Under the usual assumption that P differs from NP, established APX-completeness results therefore exclude a PTAS for the complete problem.

The reduction itself contains more information than an ordinary NP-hardness proof. A decision reduction can map nearby objective values to target instances whose optima differ by an uncontrolled amount. An AP-reduction instead maintains a quantitative relationship between solution quality before and after reconstruction. This relationship permits the classification to reflect approximability rather than only exact computational difficulty.

Completeness results depend on the chosen reduction. A problem can be complete under a permissive approximation-preserving reduction while lacking completeness under an L-reduction or another more restrictive transformation. Statements of approximation hardness therefore identify both the source class and the reduction notion.