6
$\begingroup$

What's the intuition for PTAS reductions instead of approximation preserving reductions or something of that ilk? I'd expect APX-Hardness to mean something like "finding a constant factor approximation for this problem is as hard as finding a constant factor approximation to any problem in APX" but having just a PTAS reduction from A to B isn't strong enough to imply a constant factor approx to B can be converted into a constant factor approx of A.

$\endgroup$
5
$\begingroup$

Let me correct two misconceptions in your question:

  • $PTAS$-reductions are approximation-preserving

  • $APX$ is the class of problems that have constant-factor approximations

The big open question isn't whether $APX$ problems have constant-factor approximations (by definition, they do), but whether they have polynomial time approximation schemes. The meaning of $APX$-complete is "As hard as any problem in $APX$ to find a polynomial time approximation scheme for". A $PTAS$ from $A$ to $B$ reduction allows any polynomial time approximation scheme for $B$ to be used for $A$.

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