Loading jsMath...
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