patternMinor
Why are PTAS-Reductions used to establish APX-Hardness?
Viewed 0 times
whyhardnessareusedestablishapxreductionsptas
Problem
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.
Solution
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$.
-
$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$.
Context
StackExchange Computer Science Q#46862, answer score: 5
Revisions (0)
No revisions yet.