Lower bounds for approximating the matching polytope

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We prove that any linear program 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 α= 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 [22, 5] whereas for 2/n ≤ ϵ ≤ 1, the best lower bound was 2 Ω(1/ϵ) [22]. 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.

Original languageEnglish (US)
Title of host publication29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018
EditorsArtur Czumaj
PublisherAssociation for Computing Machinery
Pages1585-1604
Number of pages20
ISBN (Electronic)9781611975031
DOIs
StatePublished - 2018
Externally publishedYes
Event29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018 - New Orleans, United States
Duration: Jan 7 2018Jan 10 2018

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018
Country/TerritoryUnited States
CityNew Orleans
Period1/7/181/10/18

ASJC Scopus subject areas

  • Software
  • General Mathematics

Fingerprint

Dive into the research topics of 'Lower bounds for approximating the matching polytope'. Together they form a unique fingerprint.

Cite this