A new semidefinite programming hierarchy for cycles in binary matroids and cuts in graphs
From MaRDI portal
(Redirected from Publication:431017)
Abstract: The theta bodies of a polynomial ideal are a series of semidefinite programming relaxations of the convex hull of the real variety of the ideal. In this paper we construct the theta bodies of the vanishing ideal of cycles in a binary matroid. Applied to cuts in graphs, this yields a new hierarchy of semidefinite programming relaxations of the cut polytope of the graph. If the binary matroid avoids certain minors we can characterize when the first theta body in the hierarchy equals the cycle polytope of the matroid. Specialized to cuts in graphs, this result solves a problem posed by Lov'asz.
Recommendations
Cites work
- scientific article; zbMATH DE number 420868 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1201576 (Why is no real title available?)
- scientific article; zbMATH DE number 1944141 (Why is no real title available?)
- scientific article; zbMATH DE number 1757962 (Why is no real title available?)
- scientific article; zbMATH DE number 2196288 (Why is no real title available?)
- A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- Compressed polytopes and statistical disclosure limitation
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Decomposition and optimization over cycles in binary matroids
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Lower Bound for the Number of Iterations in Semidefinite Hierarchies for the Cut Polytope
- Master polytopes for cycles of binary matroids
- Matching, Euler tours and the Chinese postman
- On the Shannon capacity of a graph
- On the cycle polytope of a binary matroid
- Semidefinite programming and integer programming
- Semidefinite programming relaxations for semialgebraic problems
- Semidefinite representations for finite varieties
- The max-cut problem on graphs not contractible to \(K_ 5\)
Cited in
(16)- Matrix convex hulls of free semialgebraic sets
- Theta bodies for polynomial ideals
- Computation with polynomial equations and inequalities arising in combinatorial optimization
- scientific article; zbMATH DE number 7525500 (Why is no real title available?)
- Certifying Polynomial Nonnegativity via Hyperbolic Optimization
- Theta rank, levelness, and matroid minors
- On the maximum positive semi-definite nullity and the cycle matroid of graphs
- Convex hulls of algebraic sets
- Cycle algebras and polytopes of matroids
- Tensor theta norms and low rank recovery
- Equivariant Semidefinite Lifts and Sum-of-Squares Hierarchies
- Sums of squares on the hypercube
- Linear optimization with cones of moments and nonnegative polynomials
- Mincut ideals of two-terminal networks
- A semidefinite approach to the $K_i$-cover problem
- Binary Positive Semidefinite Matrices and Associated Integer Polytopes
This page was built for publication: A new semidefinite programming hierarchy for cycles in binary matroids and cuts in graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q431017)
