Lukas' Notes

Search titles, aliases and note text. Use # for tags.

Inapproximability Transfer under Linear Reductions

4 min read

Definition

Inapproximability Transfer under Linear Reductions

Let be maximisation problems with non-negative objective values, and suppose there is a L-reduction from to with fixed constants .

For , set and assume . If has no polynomial-time -approximation algorithm, then has no polynomial-time -approximation algorithm:

Here an -approximation for maximisation returns a feasible solution of value at least on every instance. Any complexity assumption underlying the source impossibility remains in force for the target impossibility.

This is the standard approximation-transfer consequence of L-reductions; the title is descriptive rather than a unique named theorem.

Start with the Missing Value

Fix a source instance . The reduction constructs and converts a target solution back to . Write and let be the value of .

For maximisation, counts the value still missing from the optimum. The two L-reduction bounds are $$
O_2\leq\alpha O_1,
\qquad O_1-v_1\leq\beta(O_2-v_2).

You can't use 'macro parameter character #' in math mode The first bound controls the scale of the optimum. The second controls the error when converting a solution. Together they control relative error. > [!proof] A forbidden target algorithm would give a forbidden source algorithm > > > [!part] Run the hypothetical target approximation > > > > Suppose the target algorithm guarantees $v_2\geq\rho O_2$. Subtracting from $O_2$ gives > > $$O_2-v_2\leq(1-\rho)O_2.$$ > > > [!part] Convert the solution and bound its missing value > > > > Apply $g$ to obtain $x_1$. Then > > $$ > > \begin{aligned} > > O_1-v_1 > > &\leq\beta(O_2-v_2)&&\text{error conversion}\\ > > &\leq\beta(1-\rho)O_2&&\text{target approximation}\\ > > &\leq\alpha\beta(1-\rho)O_1&&\text{optimum scale}. > > \end{aligned} > > $$ > > Thus $v_1\geq[1-\alpha\beta(1-\rho)]O_1$. > > > [!part] Choose the target ratio that gives exactly $\epsilon$ > > > > We need the allowed source error to be $1-\epsilon$: > > $$ > > \begin{aligned} > > \alpha\beta(1-\rho)&=1-\epsilon,\\ > > 1-\rho&=\frac{1-\epsilon}{\alpha\beta},\\ > > \rho&=1-\frac{1-\epsilon}{\alpha\beta}. > > \end{aligned} > > $$ > > With this choice, the source algorithm guarantees $v_1\geq\epsilon O_1$. All three computations—$f$, the target algorithm, and $g$—are polynomial-time. This contradicts the source impossibility. ## Reading the Error Bound Visually For $\alpha=2$ and $\beta=1$, take $O_1=100$ and $O_2=200$. A target value of at least $190$ leaves at most $10$ missing units. The converted source value is therefore at least $90$. ```tikz \begin{document} \begin{tikzpicture}[text=cyan!30!white,font=\small] \node[anchor=west] at (0,2.1) {Target: $O_2=200$, guaranteed value $190$}; \draw[cyan!30!white,fill=cyan!10!black] (0,1) rectangle (9.5,1.6); \draw[orange!30!white,fill=orange!10!black] (9.5,1) rectangle (10,1.6); \node at (4.75,1.3) {at least $190$}; \node[anchor=west,text=orange!30!white] at (10.3,1.3) {at most $10$ missing}; \node[anchor=west] at (0,-0.1) {Source: $O_1=100$, guaranteed value $90$}; \draw[cyan!30!white,fill=cyan!10!black] (0,-1.2) rectangle (4.5,-0.6); \draw[orange!30!white,fill=orange!10!black] (4.5,-1.2) rectangle (5,-0.6); \node at (2.25,-0.9) {at least $90$}; \node[anchor=west,text=orange!30!white] at (5.3,-0.9) {at most $10$ missing}; \node[anchor=west] at (0,-2) {Same absolute error; relative error grows from $5\%$ to $10\%$.}; \end{tikzpicture} \end{document} ``` Algorithms transfer from $\Pi_2$ back to $\Pi_1$. Taking the contrapositive transfers hardness from $\Pi_1$ to $\Pi_2$. ## Boundary Ratios and Exact Hardness If the premise excludes an $\varepsilon$-approximation **at** $\varepsilon$, the theorem excludes the displayed target ratio **at** $\rho$. If instead the premise excludes only ratios strictly above $r$, the conclusion excludes only

\rho>1-\frac{1-r}{\alpha\beta}.

You can't use 'macro parameter character #' in math mode Do not silently replace one premise by the other. Setting $\epsilon=1$ gives $\rho=1$: a target optimum converts to a source optimum. Consequently an L-reduction also transfers hardness of exact optimisation. This does not mean that every ordinary Karp reduction is an L-reduction. The statements here concern deterministic polynomial-time algorithms. A randomised hardness conclusion requires an appropriate randomised source-hardness assumption. ## Example > [!example] The Max2SAT threshold > > The [[Knowledge/MaxE3SAT to Max2SAT (Linear Reduction)|MaxE3SAT to Max2SAT reduction]] has $\alpha\beta=55/7$. MaxE3SAT excludes ratios strictly above $r=7/8$ unless $P=NP$. Hence Max2SAT excludes ratios strictly above > $$ > 1-\frac{1-7/8}{55/7}=1-\frac7{440}=\frac{433}{440}. > $$ > The boundary itself is not ruled out by this premise.

Backlinks