文章基本信息

标题：Lower Bounds for Approximating the Matching Polytope
本地全文：下载
作者：Makrand Sinha
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2017
卷号：2017
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We prove that any extended formulation that approximates the matching polytope on n -vertex graphs up to a factor of (1 + ) for any 2 n 1 must have at least n defining inequalities where 0 1 is an absolute constant. This is tight as exhibited by the (1 + ) approximating linear program obtained by dropping the odd set constraints of size larger than ( 1 + ) from the description of the matching polytope. Previously, a tight lower bound of 2 ( n ) was only known for = O 1 n [Rothvoss, STOC '14; Braun and Pokutta, IEEE Trans. Information Theory '15] whereas for 2 n 1 , the best lower bound was 2 1 [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.
关键词：extended formulations ; Matching polytope ; non-negative rank ; unique disjointness matrix