Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR17-185 | 28th November 2017 08:49

Lower Bounds for Approximating the Matching Polytope

RSS-Feed




TR17-185
Authors: Makrand Sinha
Publication: 29th November 2017 06:02
Downloads: 1376
Keywords: 


Abstract:

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 program obtained by dropping the odd set constraints of size larger than ({1+\varepsilon})/{\varepsilon} from the description of the matching polytope. Previously, a tight lower bound of 2^{\Omega(n)} was only known for \varepsilon = O\left(\frac{1}{n}\right) [Rothvoss, STOC '14; Braun and Pokutta, IEEE Trans. Information Theory '15] whereas for \frac2n \le \varepsilon \le 1, the best lower bound was 2^{\Omega\left({1}/{\varepsilon}\right)} [Rothvoss, STOC '14]. The key new ingredient in our proof is a close connection to the non-negative rank of a lopsided version of the unique disjointness matrix.



ISSN 1433-8092 | Imprint