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
- 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
- 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?)
- 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 cycle polytope of a binary matroid
- On the Shannon capacity of a graph
- 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)- A semidefinite approach to the $K_i$-cover problem
- Tensor theta norms and low rank recovery
- Matrix convex hulls of free semialgebraic sets
- Convex hulls of algebraic sets
- Computation with polynomial equations and inequalities arising in combinatorial optimization
- Theta bodies for polynomial ideals
- Sums of squares on the hypercube
- On the maximum positive semi-definite nullity and the cycle matroid of graphs
- Equivariant Semidefinite Lifts and Sum-of-Squares Hierarchies
- Binary Positive Semidefinite Matrices and Associated Integer Polytopes
- Theta rank, levelness, and matroid minors
- scientific article; zbMATH DE number 7525500 (Why is no real title available?)
- Certifying Polynomial Nonnegativity via Hyperbolic Optimization
- Mincut ideals of two-terminal networks
- Cycle algebras and polytopes of matroids
- Linear optimization with cones of moments and nonnegative polynomials
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)
