Lower Bound for the Number of Iterations in Semidefinite Hierarchies for the Cut Polytope
From MaRDI portal
(Redirected from Publication:5704154)
Recommendations
- scientific article; zbMATH DE number 2196288
- Tighter linear and semidefinite relaxations for max-cut based on the Lovász-Schrijver lift-and-project procedure
- A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
- On the matrix-cut rank of polyhedra.
- Semidefinite bounds for the stability number of a graph via sums of squares of polynomials
Cited in
(35)- A semidefinite approach to the $K_i$-cover problem
- An unbounded sum-of-squares hierarchy integrality gap for a polynomially solvable problem
- Binary quadratic optimization problems that are difficult to solve by conic relaxations
- On self-regular IPMs (with comments and rejoinder)
- Optimization over the Boolean hypercube via sums of nonnegative circuit polynomials
- A tight degree 4 sum-of-squares lower bound for the Sherrington-Kirkpatrick Hamiltonian
- Completely positive reformulations for polynomial optimization
- Unification of lower-bound analyses of the lift-and-project rank of combinatorial optimization polyhedra
- Tighter linear and semidefinite relaxations for max-cut based on the Lovász-Schrijver lift-and-project procedure
- Sums of squares on the hypercube
- Query complexity in expectation
- Sparse sums of squares on finite abelian groups and improved semidefinite lifts
- Equivariant Semidefinite Lifts and Sum-of-Squares Hierarchies
- A new semidefinite programming hierarchy for cycles in binary matroids and cuts in graphs
- scientific article; zbMATH DE number 7378399 (Why is no real title available?)
- Disordered systems insights on computational hardness
- Sum of squares lower bounds from symmetry and a good story
- Sum-of-squares bounds via Boolean function analysis
- Computation of the Lasserre Ranks of Some Polytopes
- scientific article; zbMATH DE number 2196288 (Why is no real title available?)
- Exact Semidefinite Programming Relaxations with Truncated Moment Matrix for Binary Polynomial Optimization Problems
- Sum-of-squares hierarchies for binary polynomial optimization
- Sum-of-squares hierarchies for binary polynomial optimization
- Sum of Squares Bounds for the Empty Integral Hull Problem
- The Spectrum of the Grigoriev–Laurent Pseudomoments
- Loraine – an interior-point solver for low-rank semidefinite programming
- On the numerical solution of Lasserre relaxations of unconstrained binary quadratic optimization problem
- On rank-monotone graph operations and minimal obstruction graphs for the Lovász-Schrijver SDP hierarchy
- Tight sum-of-squares lower bounds for binary polynomial optimization problems
- SoS certification for symmetric quadratic functions and its connection to constrained Boolean hypercube optimization
- On the bit size of sum-of-squares proofs for symmetric formulations
- Convergence of the sum-of-squares hierarchy for quadratic optimization over roots-of-unity
- Linear programming hierarchies collapse under symmetry
- Semidefinite representations for finite varieties
- The equivalence of semidefinite relaxations of polynomial 0-1 and 1 programs via scaling
This page was built for publication: Lower Bound for the Number of Iterations in Semidefinite Hierarchies for the Cut Polytope
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5704154)
