Lower Bounds for Approximating the Matching Polytope

Makrand Sinha

We prove that any extended formulation that approximates the matching polytope on $n$-vertex graphs up to a factor of $(1+\epsilon )$ for any $\frac{2}{n}\le \epsilon \le 1$ must…