Extending SDP Integrality Gaps to Sherali-Adams with Applications to Quadratic Programming and MaxCutGain

DOI10.1007/978-3-642-13036-6_23zbMath1285.90028OpenAlexW1585955818MaRDI QIDQ3569826

Siavosh Benabbas, Avner Magen

Publication date: 22 June 2010

Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-13036-6_23

Mathematics Subject Classification ID

Semidefinite programming (90C22) Integer programming (90C10) Quadratic programming (90C20)

Related Items (7)

A bounded degree SOS hierarchy for polynomial optimization ⋮ Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack ⋮ A Comprehensive Analysis of Polyhedral Lift-and-Project Methods ⋮ Exponential Lower Bounds for Polytopes in Combinatorial Optimization ⋮ Uncapacitated flow-based extended formulations ⋮ Hypercontractive inequalities via SOS, and the Frankl--Rödl graph ⋮ Superlinear Integrality Gaps for the Minimum Majority Problem

This page was built for publication: Extending SDP Integrality Gaps to Sherali-Adams with Applications to Quadratic Programming and MaxCutGain