Lower Bound for the Number of Iterations in Semidefinite Hierarchies for the Cut Polytope

DOI10.1287/moor.28.4.871.20508zbMath1082.90085OpenAlexW2168417806MaRDI QIDQ5704154

Monique Laurent

Publication date: 11 November 2005

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/61804c14cf4ebcec23ec687135de7d6c960f732c

zbMATH Keywords

moment matrixsemidefinite relaxationCut polytoperank of lift-and-project method

Mathematics Subject Classification ID

Semidefinite programming (90C22) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Boolean programming (90C09) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Query Complexity in Expectation, Equivariant Semidefinite Lifts and Sum-of-Squares Hierarchies, Disordered systems insights on computational hardness, Optimization over the Boolean hypercube via sums of nonnegative circuit polynomials, Sums of squares on the hypercube, Sparse sums of squares on finite abelian groups and improved semidefinite lifts, Semidefinite representations for finite varieties, A semidefinite approach to the $K_i$-cover problem, An unbounded sum-of-squares hierarchy integrality gap for a polynomially solvable problem, Sum of Squares Bounds for the Empty Integral Hull Problem, Sum-of-squares hierarchy lower bounds for symmetric formulations, Breaking symmetries to rescue sum of squares in the case of makespan scheduling, The Spectrum of the Grigoriev–Laurent Pseudomoments, Unnamed Item, A new semidefinite programming hierarchy for cycles in binary matroids and cuts in graphs, Unification of lower-bound analyses of the lift-and-project rank of combinatorial optimization polyhedra, A tight degree 4 sum-of-squares lower bound for the Sherrington-Kirkpatrick Hamiltonian, The equivalence of semidefinite relaxations of polynomial 0-1 and \(\pm 1\) programs via scaling, Binary quadratic optimization problems that are difficult to solve by conic relaxations, Exact Semidefinite Programming Relaxations with Truncated Moment Matrix for Binary Polynomial Optimization Problems, On self-regular IPMs (with comments and rejoinder), Unnamed Item, Unnamed Item, Sum-of-squares hierarchies for binary polynomial optimization, Sum-of-squares hierarchies for binary polynomial optimization, Completely positive reformulations for polynomial optimization