l-reduction

Let A and B be optimization problems and c_A and c_B their respective cost functions. A pair of functions f and g is an L-reduction if all of the following conditions are met:

• functions f and g are computable in polynomial time,
• if x is an instance of problem A, then f(x) is an instance of problem B,
• if y' is a solution to f(x), then g(y' ) is a solution to x,
• there exists a positive constant α such that

:$\backslash mathrm\{OPT\_B\}(f(x))\; \backslash le\; \backslash alpha\; \backslash mathrm\{OPT\_A\}(x)$,

• there exists a positive constant β such that for every solution y' to f(x)

:$|\backslash mathrm\{OPT\_A\}(x)-c\_A(g(y\text{'}))|\; \backslash le\; \backslash beta\; |\backslash mathrm\{OPT\_B\}(f(x))-c\_B(y\text{'})|$.

An L-reduction from problem A to problem B implies an AP-reduction when A and B are minimization problems and a PTAS reduction when A and B are maximization problems. In both cases, when B has a PTAS and there is an L-reduction from A to B, then A also has a PTAS.{{cite book

| last1 = Kann | first1 = Viggo

| year = 1992

| title = On the Approximability of NP-complete \mathrm{OPT}imization Problems

| publisher = Royal Institute of Technology, Sweden

| isbn = 978-91-7170-082-7

}}{{cite conference

| author= Christos H. Papadimitriou

|author2=Mihalis Yannakakis

| book-title = STOC '88: Proceedings of the twentieth annual ACM Symposium on Theory of Computing

| title = \mathrm{OPT}imization, Approximation, and Complexity Classes

| year = 1988

| doi = 10.1145/62212.62233

| doi-access = free

}} This enables the use of L-reduction as a replacement for showing the existence of a PTAS-reduction; Crescenzi has suggested that the more natural formulation of L-reduction is actually more useful in many cases due to ease of usage.{{cite book|last1=Crescenzi|first1=Pierluigi|title=Proceedings of Computational Complexity. Twelfth Annual IEEE Conference |chapter=A short guide to approximation preserving reductions |date=1997|pages=262–|chapter-url=http://dl.acm.org/citation.cfm?id=792302|publisher=IEEE Computer Society|location=Washington, D.C.|doi=10.1109/CCC.1997.612321 |isbn=9780818679070 |s2cid=18911241 }}

Let the approximation ratio of B be $1\; +\; \backslash delta$.

Begin with the approximation ratio of A, $\backslash frac\{c\_A(y)\}\{\backslash mathrm\{OPT\}\_A(x)\}$.

We can remove absolute values around the third condition of the L-reduction definition since we know A and B are minimization problems. Substitute that condition to obtain

: $\backslash frac\{c\_A(y)\}\{\backslash mathrm\{OPT\}\_A(x)\}\; \backslash le\; \backslash frac\{\backslash mathrm\{OPT\}\_A(x)\; +\; \backslash beta(c\_B(y\text{'})\; -\; \backslash mathrm\{OPT\}\_B(x\text{'}))\}\{\backslash mathrm\{OPT\}\_A(x)\}$

Simplifying, and substituting the first condition, we have

: $\backslash frac\{c\_A(y)\}\{\backslash mathrm\{OPT\}\_A(x)\}\; \backslash le\; 1\; +\; \backslash alpha\; \backslash beta\; \backslash left(\; \backslash frac\{c\_B(y\text{'})-\backslash mathrm\{OPT\}\_B(x\text{'})\}\{\backslash mathrm\{OPT\}\_B(x\text{'})\}\; \backslash right)$

But the term in parentheses on the right-hand side actually equals $\backslash delta$. Thus, the approximation ratio of A is $1\; +\; \backslash alpha\backslash beta\backslash delta$.

This meets the conditions for AP-reduction.

Let the approximation ratio of B be $\backslash frac\{1\}\{1\; -\; \backslash delta\text{'}\}$.

Begin with the approximation ratio of A, $\backslash frac\{c\_A(y)\}\{\backslash mathrm\{OPT\}\_A(x)\}$.

We can remove absolute values around the third condition of the L-reduction definition since we know A and B are maximization problems. Substitute that condition to obtain

: $\backslash frac\{c\_A(y)\}\{\backslash mathrm\{OPT\}\_A(x)\}\; \backslash ge\; \backslash frac\{\backslash mathrm\{OPT\}\_A(x)\; -\; \backslash beta(c\_B(y\text{'})\; -\; \backslash mathrm\{OPT\}\_B(x\text{'}))\}\{\backslash mathrm\{OPT\}\_A(x)\}$

Simplifying, and substituting the first condition, we have

: $\backslash frac\{c\_A(y)\}\{\backslash mathrm\{OPT\}\_A(x)\}\; \backslash ge\; 1\; -\; \backslash alpha\; \backslash beta\; \backslash left(\; \backslash frac\{c\_B(y\text{'})-\backslash mathrm\{OPT\}\_B(x\text{'})\}\{\backslash mathrm\{OPT\}\_B(x\text{'})\}\; \backslash right)$

But the term in parentheses on the right-hand side actually equals $\backslash delta\text{'}$. Thus, the approximation ratio of A is $\backslash frac\{1\}\{1\; -\; \backslash alpha\backslash beta\backslash delta\text{'}\}$.

If $\backslash frac\{1\}\{1\; -\; \backslash alpha\backslash beta\backslash delta\text{'}\}\; =\; 1+\backslash epsilon$, then $\backslash frac\{1\}\{1\; -\; \backslash delta\text{'}\}\; =\; 1\; +\; \backslash frac\{\backslash epsilon\}\{\backslash alpha\backslash beta(1+\backslash epsilon)\; -\; \backslash epsilon\}$, which meets the requirements for PTAS reduction but not AP-reduction.

L-reductions also imply P-reduction. One may deduce that L-reductions imply PTAS reductions from this fact and the fact that P-reductions imply PTAS reductions.

L-reductions preserve membership in APX for the minimizing case only, as a result of implying AP-reductions.

• Dominating set: an example with α = β = 1
• Token reconfiguration: an example with α = 1/5, β = 2

• MAXSNP
• Approximation-preserving reduction
• PTAS reduction

{{reflist}}

• G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi. Complexity and Approximation. Combinatorial optimization problems and their approximability properties. 1999, Springer. {{isbn|3-540-65431-3}}

{{comp-sci-theory-stub}}

Category:Reduction (complexity)

Category:Approximation algorithms