Optimal Sherali-Adams Gaps from Pairwise Independence

DOI10.1007/978-3-642-03685-9_10MaRDI QIDQ3638873zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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

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

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
• Uncapacitated flow-based extended formulations
• Superlinear Integrality Gaps for the Minimum Majority Problem
• 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)