Optimal Sherali-Adams Gaps from Pairwise Independence

DOI10.1007/978-3-642-03685-9_10zbMath1254.68125OpenAlexW1485993952MaRDI QIDQ3638873

Konstantinos Georgiou, Madhur Tulsiani, Avner Magen

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

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

Related Items (8)

Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems ⋮ Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack ⋮ Exponential Lower Bounds for Polytopes in Combinatorial Optimization ⋮ Convex Relaxations and Integrality Gaps ⋮ Uncapacitated flow-based extended formulations ⋮ No Small Linear Program Approximates Vertex Cover Within a Factor 2 − ɛ ⋮ Unnamed Item ⋮ Superlinear Integrality Gaps for the Minimum Majority Problem

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