Optimal Sherali-Adams Gaps from Pairwise Independence

DOI10.1007/978-3-642-03685-9_10zbMATH Open1254.68125OpenAlexW1485993952MaRDI QIDQ3638873FDOQ3638873

Authors: Konstantinos Georgiou, Avner Magen, Madhur Tulsiani 

Publication date: 28 October 2009

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-03685-9_10

Recommendations

• SDP gaps from pairwise independence
• From weak to strong LP gaps for all CSPs
• Approximation resistant predicates from pairwise independence
• Sum of squares lower bounds from pairwise independence (extended abstract)
• From weak to strong linear programming gaps for all constraint satisfaction problems

Mathematics Subject Classification ID

Linear programming (90C05) Semidefinite programming (90C22) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cited In (11)

• Approximation schemes via Sherali-Adams hierarchy for dense constraint satisfaction problems and assignment problems
• SDP gaps from pairwise independence
• Exponential lower bounds for polytopes in combinatorial optimization
• Integrality gaps of linear and semi-definite programming relaxations for knapsack
• Superlinear Integrality Gaps for the Minimum Majority Problem
• Uncapacitated flow-based extended formulations
• Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems
• No small linear program approximates vertex cover within a factor \(2 -\varepsilon\)
• Convex relaxations and integrality gaps
• Sum of squares lower bounds from pairwise independence (extended abstract)
• Polynomial integrality gaps for strong SDP relaxations of densest \(k\)-subgraph

This page was built for publication: Optimal Sherali-Adams Gaps from Pairwise Independence

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3638873)