2
$\begingroup$

I was reading about $L$-reductions and there was one part in the definition that I thought was interesting. I wanted to know what motivated people who came up with it to have it included in the definition.

Recall that a problem $A$ is $L$-reducible to another problem $B$ if there exist polynomial-time computable functions $f$ and $g$, and positive constants $\alpha$ and $\beta$ such that:

  1. If $x$ is an instance of problem $A$, then $f(x)$ is an instance of problem $B$.
  2. If $y'$ is a solution to the instance $f(x)$ of problem $B$, then $g(y')$ is a solution to the instance $x$ of problem $A$.
  3. $OPT_B(f(x)) \leq \alpha OPT_A(x)$.
  4. $|c_A(g(y'))-OPT_A(x)| \leq \beta |c_B(y')-OPT_B(f(x))|$.

where $c_A$ and $c_B$ are the cost functions for the problems $A$ and $B$, and $OPT_A$ and $OPT_B$ have their usual meanings.

Points 1, 2, and 4 seem completely natural to me. We want some way to map instances of $A$ to instances of $B$ in polynomial time. $f$ takes care of that. Additionally, we want some way (again in polynomial time) to map solutions to instances of $B$ to solutions to instances of $A$. $g$ takes care of that. Finally, we want the mapped solutions to preserve some notion of "quality" so that we can make statements like "if $y'$ is a "good" solution, then $g(y')$ is not "too bad" of a solution". Point 4 takes care of that. But what do we need point 3 for? It seems to me that points 1, 2 and 4 suffice for the definition of a "natural" approximation-preserving reduction.

I know that for $L$-reducibility to imply $PTAS$-reducibility, we need point 3. But is that the only reason for adding point 3 to the definition?

$\endgroup$
3
  • 1
    $\begingroup$ It seems that your question already contains a complete answer. $\endgroup$ – Yuval Filmus Sep 30 '20 at 15:23
  • $\begingroup$ @YuvalFilmus, Ah, so the motivation for $L$-reductions is to have an easy-to-work-with reduction that also implies PTAS-reducibility? $\endgroup$ – mursalin Sep 30 '20 at 15:38
  • $\begingroup$ That sounds like a good motivation. I don't know whether that was the original motivation, but it seems likely. $\endgroup$ – Yuval Filmus Sep 30 '20 at 15:46
2
$\begingroup$

L-reductions were defined by Papadimitriou and Yannakakis in their paper Optimization, approximation, and complexity classes. From the abstract:

Furthermore, we show that a number of common optimization problems are complete for MAXSNP under a kind of careful transformation (called L-reduction) that preserves approximability.

A survey of various related notions of reducibility is Ausiello and Paschos, Approximability preserving reduction. Each of the notions of reductions appearing there was invented to serve some purpose. Definitions are typically not arbitrary. They are supposed to model some intuitive notion. Some definitions are more successful than others. When unsure about a definition, it's always a good idea to check out the original paper(s) introducing the definition.

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