Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > MATCHING POLYTOPE:
Reports tagged with Matching polytope:
TR17-185 | 28th November 2017
Makrand Sinha

Lower Bounds for Approximating the Matching Polytope

We prove that any extended formulation that approximates the matching polytope on $n$-vertex graphs up to a factor of $(1+\varepsilon)$ for any $\frac2n \le \varepsilon \le 1$ must have at least ${n}\choose{{\alpha}/{\varepsilon}}$ defining inequalities where $0<\alpha<1$ is an absolute constant. This is tight as exhibited by the $(1+\varepsilon)$ approximating linear ... more >>>




ISSN 1433-8092 | Imprint