Integrality gaps for Sherali-Adams relaxations

DOI10.1145/1536414.1536455zbMath1304.90143MaRDI QIDQ5172722

Yury Makarychev, Moses Charikar, Konstantin Makarychev

Publication date: 4 February 2015

Published in: Proceedings of the forty-first annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1536414.1536455

zbMATH Keywords

Sherali-Adams hierarchy; lift-and-project methods; local-global metric spaces

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

90C10: Integer programming

90C57: Polyhedral combinatorics, branch-and-bound, branch-and-cut

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

Improved Approximation Guarantees through Higher Levels of SDP Hierarchies