Integrality gaps for Sherali-Adams relaxations

DOI10.1145/1536414.1536455zbMath1304.90143OpenAlexW2083858754MaRDI QIDQ5172722

Konstantin Makarychev, Yury Makarychev, Moses Charikar

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 hierarchylift-and-project methodslocal-global metric spaces

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (30)

Approximation Limits of Linear Programs (Beyond Hierarchies) ⋮ Integrality gaps for strengthened linear relaxations of capacitated facility location ⋮ On integrality ratios for asymmetric TSP in the Sherali-Adams hierarchy ⋮ Communication Lower Bounds via Critical Block Sensitivity ⋮ On the approximability of digraph ordering ⋮ Rank of Handelman hierarchy for Max-Cut ⋮ Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems ⋮ Towards strong nonapproximability results in the Lovász-Schrijver hierarchy ⋮ Affine reductions for LPs and SDPs ⋮ Improved Approximation Guarantees through Higher Levels of SDP Hierarchies ⋮ Rank bounds for a hierarchy of Lovász and Schrijver ⋮ Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack ⋮ Lift \& project systems performing on the partial-vertex-cover polytope ⋮ On linear and semidefinite programming relaxations for hypergraph matching ⋮ A Comprehensive Analysis of Polyhedral Lift-and-Project Methods ⋮ Unnamed Item ⋮ Exponential Lower Bounds for Polytopes in Combinatorial Optimization ⋮ Convex Relaxations and Integrality Gaps ⋮ Strong reductions for extended formulations ⋮ Uncapacitated flow-based extended formulations ⋮ No Small Linear Program Approximates Vertex Cover Within a Factor 2 − ɛ ⋮ Union of Euclidean Metric Spaces is Euclidean ⋮ Hypercontractive inequalities via SOS, and the Frankl--Rödl graph ⋮ Sherali-adams strikes back ⋮ Approximating Rectangles by Juntas and Weakly Exponential Lower Bounds for LP Relaxations of CSPs ⋮ Unnamed Item ⋮ Sherali-Adams relaxations of graph isomorphism polytopes ⋮ Symmetry-exploiting cuts for a class of mixed-\(0/1\) second-order cone programs ⋮ Unnamed Item ⋮ Superlinear Integrality Gaps for the Minimum Majority Problem

This page was built for publication: Integrality gaps for Sherali-Adams relaxations