Talk:L-reduction

untitled

I think that the property is false. we must write:

... there exists a polynomial ε-approximation algorithm for B then there also exists a polynomial δ-approximation algorithm for A where ...

You are correct.

The page has been fixed. Thanks for your comment :-)

Esoth, 26 May 2007, 22:23 CEST

Proof (or reference for the proof) of the property missing

Where is the proof/reference for that property? Note that the book of Papadimitriou just proves $\delta = \alpha \beta \epsilon / (1-\epsilon)$. —Preceding unsigned comment added by 130.149.15.224 (talk) 09:28, 8 April 2008 (UTC)

More references added. Do note that in Papadimitriou's book, an ε-approximation guarantees that ${\frac {|OPT-c(A(x))|}{\max(OPT,c(A(x)))}}\leq \epsilon$ (where c(A(x)) is the cost of the approximate solution) while the definition for Kann's thesis and the original paper (from the introduction), ${\frac {|OPT-c(A(x))|}{OPT}}\leq \epsilon$. —C. lorenz (talk) 00:23, 2 April 2009 (UTC)

Improve definition

The definition could be improved by adding the correct quantifiers to the last two items: "for any instance $x$ of $A$" and "for any instance $x$ of $A$ and any feasible solution $y$ of $R(x)$".

Should g also depend on x as well? see https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-890-algorithmic-lower-bounds-fun-with-hardness-proofs-fall-2014/lecture-videos/lecture-10-inapproximabililty-overview/ — Preceding unsigned comment added by 192.159.178.211 (talk) 17:20, 10 January 2020 (UTC)