Affine reductions for LPs and SDPs

Understand

We define a reduction mechanism for LP and SDP formulations that degrades approximation factors in a controlled fashion.

• Our reduction mechanism is a minor restriction of classical reductions establishing inapproximability in the context of PCP theorems.
• As a consequence we establish strong linear programming inapproximability (for LPs with a polynomial number of constraints) for many problems.
• In particular we obtain a $3/2-\varepsilon$ inapproximability for VertexCover answering an open question in [arXiv:1309.0563] and we answer a weak version of our sparse graph conjecture posed in [arXiv:1311.4001] showing an inapproximability factor of $1/2+\varepsilon$ for bounded degree IndependentSet.